src/HOL/Number_Theory/Gauss.thy
changeset 58410 6d46ad54a2ab
parent 58288 87b59745dd6d
child 58645 94bef115c08f
equal deleted inserted replaced
58409:24096e89c131 58410:6d46ad54a2ab
   316 qed
   316 qed
   317 
   317 
   318 
   318 
   319 subsection {* Gauss' Lemma *}
   319 subsection {* Gauss' Lemma *}
   320 
   320 
   321 lemma aux: "setprod id A * -1 ^ card E * a ^ card A * -1 ^ card E = setprod id A * a ^ card A"
   321 lemma aux: "setprod id A * (- 1) ^ card E * a ^ card A * (- 1) ^ card E = setprod id A * a ^ card A"
   322 by (metis (no_types) minus_minus mult.commute mult.left_commute power_minus power_one)
   322 by (metis (no_types) minus_minus mult.commute mult.left_commute power_minus power_one)
   323 
   323 
   324 theorem pre_gauss_lemma:
   324 theorem pre_gauss_lemma:
   325   "[a ^ nat((int p - 1) div 2) = (-1) ^ (card E)] (mod p)"
   325   "[a ^ nat((int p - 1) div 2) = (-1) ^ (card E)] (mod p)"
   326 proof -
   326 proof -
   361     done
   361     done
   362   then have "[setprod id A * (-1)^(card E) = setprod id A * a^(card A)](mod p)"
   362   then have "[setprod id A * (-1)^(card E) = setprod id A * a^(card A)](mod p)"
   363     apply (rule cong_trans_int)
   363     apply (rule cong_trans_int)
   364     apply (simp add: aux cong del:setprod.cong)
   364     apply (simp add: aux cong del:setprod.cong)
   365     done
   365     done
   366   with A_prod_relprime have "[-1 ^ card E = a ^ card A](mod p)"
   366   with A_prod_relprime have "[(- 1) ^ card E = a ^ card A](mod p)"
   367     by (metis cong_mult_lcancel_int)
   367     by (metis cong_mult_lcancel_int)
   368   then show ?thesis
   368   then show ?thesis
   369     by (simp add: A_card_eq cong_sym_int)
   369     by (simp add: A_card_eq cong_sym_int)
   370 qed
   370 qed
   371 
   371