equal
deleted
inserted
replaced
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" |