src/HOL/Number_Theory/Quadratic_Reciprocity.thy
changeset 68631 bc1369804692
parent 68224 1f7308050349
child 68634 db0980691ef4
equal deleted inserted replaced
68628:958511f53de8 68631:bc1369804692
   368     then have "x \<le> int p * (int q - 1) div 2 + (int p - 1) div 2"
   368     then have "x \<le> int p * (int q - 1) div 2 + (int p - 1) div 2"
   369       unfolding BuDuF_def using p_eq2 int_distrib(4) by auto
   369       unfolding BuDuF_def using p_eq2 int_distrib(4) by auto
   370     moreover from x have "(int p - 1) div 2 \<le> - 1 + x mod p"
   370     moreover from x have "(int p - 1) div 2 \<le> - 1 + x mod p"
   371       by (auto simp: BuDuF_def)
   371       by (auto simp: BuDuF_def)
   372     moreover have "int p * (int q - 1) div 2 = int p * ((int q - 1) div 2)"
   372     moreover have "int p * (int q - 1) div 2 = int p * ((int q - 1) div 2)"
   373       using zdiv_zmult1_eq odd_q by auto
   373       using div_mult1_eq odd_q by auto
   374     then have "p * (int q - 1) div 2 = p * ((int q + 1) div 2 - 1)"
   374     then have "p * (int q - 1) div 2 = p * ((int q + 1) div 2 - 1)"
   375       by fastforce
   375       by fastforce
   376     ultimately have "x \<le> p * ((int q + 1) div 2 - 1) - 1 + x mod p"
   376     ultimately have "x \<le> p * ((int q + 1) div 2 - 1) - 1 + x mod p"
   377       by linarith
   377       by linarith
   378     then have "x div p < (int q + 1) div 2 - 1"
   378     then have "x div p < (int q + 1) div 2 - 1"
   407     then obtain x where x: "x \<in> Res_h p \<times> Res_l q" and y: "y = g_3 x"
   407     then obtain x where x: "x \<in> Res_h p \<times> Res_l q" and y: "y = g_3 x"
   408       by blast
   408       by blast
   409     then have "snd x \<le> (int q - 1) div 2"
   409     then have "snd x \<le> (int q - 1) div 2"
   410       by force
   410       by force
   411     moreover have "int p * ((int q - 1) div 2) = (int p * int q - int p) div 2"
   411     moreover have "int p * ((int q - 1) div 2) = (int p * int q - int p) div 2"
   412       using int_distrib(4) zdiv_zmult1_eq[of "int p" "int q - 1" 2] odd_q by fastforce
   412       using int_distrib(4) div_mult1_eq[of "int p" "int q - 1" 2] odd_q by fastforce
   413     ultimately have "(snd x) * int p \<le> (int q * int p - int p) div 2"
   413     ultimately have "(snd x) * int p \<le> (int q * int p - int p) div 2"
   414       using mult_right_mono[of "snd x" "(int q - 1) div 2" p] mult.commute[of "(int q - 1) div 2" p]
   414       using mult_right_mono[of "snd x" "(int q - 1) div 2" p] mult.commute[of "(int q - 1) div 2" p]
   415         pq_commute
   415         pq_commute
   416       by presburger
   416       by presburger
   417     then have "(snd x - 1) * int p \<le> (int q * int p - 1) div 2 - int p"
   417     then have "(snd x - 1) * int p \<le> (int q * int p - 1) div 2 - int p"