equal
deleted
inserted
replaced
73 from assms(1,2,4) have "[MultInv p j * j = 1] (mod p)" |
73 from assms(1,2,4) have "[MultInv p j * j = 1] (mod p)" |
74 by (simp add: MultInv_prop2a) |
74 by (simp add: MultInv_prop2a) |
75 from this and a show ?thesis |
75 from this and a show ?thesis |
76 by (auto simp add: zcong_zmult_prop2) |
76 by (auto simp add: zcong_zmult_prop2) |
77 qed |
77 qed |
78 then have "[j^2 = a] (mod p)" by (simp add: power2_eq_square) |
78 then have "[j\<^sup>2 = a] (mod p)" by (simp add: power2_eq_square) |
79 with assms show False by (simp add: QuadRes_def) |
79 with assms show False by (simp add: QuadRes_def) |
80 qed |
80 qed |
81 |
81 |
82 lemma MultInvPair_card_two: "[| zprime p; 2 < p; ~([a = 0] (mod p)); |
82 lemma MultInvPair_card_two: "[| zprime p; 2 < p; ~([a = 0] (mod p)); |
83 ~(QuadRes p a); ~([j = 0] (mod p)) |] ==> |
83 ~(QuadRes p a); ~([j = 0] (mod p)) |] ==> |
267 apply (frule zcong_zmult_prop1, auto) |
267 apply (frule zcong_zmult_prop1, auto) |
268 done |
268 done |
269 |
269 |
270 text {* \medskip Prove the final part of Euler's Criterion: *} |
270 text {* \medskip Prove the final part of Euler's Criterion: *} |
271 |
271 |
272 lemma aux__1: "[| ~([x = 0] (mod p)); [y ^ 2 = x] (mod p)|] ==> ~(p dvd y)" |
272 lemma aux__1: "[| ~([x = 0] (mod p)); [y\<^sup>2 = x] (mod p)|] ==> ~(p dvd y)" |
273 by (metis dvdI power2_eq_square zcong_sym zcong_trans zcong_zero_equiv_div dvd_trans) |
273 by (metis dvdI power2_eq_square zcong_sym zcong_trans zcong_zero_equiv_div dvd_trans) |
274 |
274 |
275 lemma aux__2: "2 * nat((p - 1) div 2) = nat (2 * ((p - 1) div 2))" |
275 lemma aux__2: "2 * nat((p - 1) div 2) = nat (2 * ((p - 1) div 2))" |
276 by (auto simp add: nat_mult_distrib) |
276 by (auto simp add: nat_mult_distrib) |
277 |
277 |