src/HOL/Number_Theory/Quadratic_Reciprocity.thy

     moreover from mod k have "(p_inv * (p * kx)) mod q = (p_inv * (p * ky)) mod q"
       using mod_mult_cong by blast
     then have "(p * p_inv * kx) mod q = (p * p_inv * ky) mod q"
       by (simp add: algebra_simps)
     then have "kx mod q = ky mod q"
-      using p_inv mod_mult_cong[of "p * p_inv" "q" "1"] by (auto simp: cong_int_def)
+      using p_inv mod_mult_cong[of "p * p_inv" "q" "1"]
+      by (auto simp: cong_def)
     then have "[kx = ky] (mod q)"
-      unfolding cong_int_def by blast
+      unfolding cong_def by blast
     ultimately show ?thesis
       using cong_less_imp_eq_int k by blast
   qed
   then have "inj_on (\<lambda>x. x mod q) E"
     by (auto simp: inj_on_def)

   assumes "0 \<le> fst res" "fst res < p" "0 \<le> snd res" "snd res < q"
   shows "\<exists>!x. P_1 res x"
 proof -
   obtain y k1 k2 where yk: "y = nat (fst res) + k1 * p" "y = nat (snd res) + k2 * q"
     using chinese_remainder[of p q] pq_coprime p_ge_0 q_ge_0 by fastforce
-  have *: "[y = fst res] (mod p)" "[y = snd res] (mod q)"
-    using yk(1) assms(1) cong_iff_lin_int[of "fst res"] cong_sym_int apply simp
-    using yk(2) assms(3) cong_iff_lin_int[of "snd res"] cong_sym_int by simp
-  have "(y mod (int p * int q)) mod int p = fst res" "(y mod (int p * int q)) mod int q = snd res"
-    using *(1) mod_mod_cancel[of "int p"] assms(1) assms(2) cong_int_def apply simp
-    using *(2) mod_mod_cancel[of "int q"] assms(3) assms(4) cong_int_def by simp
+  have "fst res = int (y - k1 * p)"
+    using \<open>0 \<le> fst res\<close> yk(1) by simp
+  moreover have "snd res = int (y - k2 * q)"
+    using \<open>0 \<le> snd res\<close> yk(2) by simp
+  ultimately have res: "res = (int (y - k1 * p), int (y - k2 * q))"
+    by (simp add: prod_eq_iff)
+  have y: "k1 * p \<le> y" "k2 * q \<le> y"
+    using yk by simp_all
+  from y have *: "[y = nat (fst res)] (mod p)" "[y = nat (snd res)] (mod q)"
+    by (auto simp add: res cong_le_nat intro: exI [of _ k1] exI [of _ k2])
+  from * have "(y mod (int p * int q)) mod int p = fst res" "(y mod (int p * int q)) mod int q = snd res"
+    using y apply (auto simp add: res of_nat_mult [symmetric] of_nat_mod [symmetric] mod_mod_cancel simp del: of_nat_mult)
+     apply (metis \<open>fst res = int (y - k1 * p)\<close> assms(1) assms(2) cong_def mod_pos_pos_trivial nat_int of_nat_mod)
+    apply (metis \<open>snd res = int (y - k2 * q)\<close> assms(3) assms(4) cong_def mod_pos_pos_trivial nat_int of_nat_mod)
+    done
   then obtain x where "P_1 res x"
     unfolding P_1_def
     using Divides.pos_mod_bound Divides.pos_mod_sign pq_ge_0 by fastforce
   moreover have "a = b" if "P_1 res a" "P_1 res b" for a b
   proof -

 qed
 
 lemma QR_lemma_08:
     "f_2 x mod p \<in> Res_l p \<longleftrightarrow> x mod p \<in> Res_h p"
     "f_2 x mod p \<in> Res_h p \<longleftrightarrow> x mod p \<in> Res_l p"
-  using f_2_lemma_2[of x] cong_int_def[of "f_2 x" "p - x" p] minus_mod_self2[of x p]
+  using f_2_lemma_2[of x] cong_def[of "f_2 x" "p - x" p] minus_mod_self2[of x p]
     zmod_zminus1_eq_if[of x p] p_eq2
   by auto
 
 lemma QR_lemma_09:
     "f_2 x mod q \<in> Res_l q \<longleftrightarrow> x mod q \<in> Res_h q"

     have *: "f_3 (g_3 x) = x" if "x \<in> Res_h p \<times> Res_l q" for x
     proof -
       from that have *: "(fst x + (snd x - 1) * int p) mod int p = fst x"
         by force
       from that have "(fst x + (snd x - 1) * int p) div int p + 1 = snd x"
-        by (auto simp: div_pos_pos_trivial)
+        by auto
       with * show "f_3 (g_3 x) = x"
         by (simp add: f_3_def g_3_def)
     qed
     fix x y
     assume "x \<in> Res_h p \<times> Res_l q" "y \<in> Res_h p \<times> Res_l q" "g_3 x = g_3 y"