src/HOL/Old_Number_Theory/Euler.thy
changeset 53077 a1b3784f8129
parent 45480 a39bb6d42ace
child 57418 6ab1c7cb0b8d
equal deleted inserted replaced
53076:47c9aff07725 53077:a1b3784f8129
    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