src/HOL/Number_Theory/Residues.thy
changeset 63417 c184ec919c70
parent 63167 0909deb8059b
child 63534 523b488b15c9
equal deleted inserted replaced
63416:6af79184bef3 63417:c184ec919c70
   424   also have "\<dots> = (\<Prod>i\<in>Units R. i) mod p"
   424   also have "\<dots> = (\<Prod>i\<in>Units R. i) mod p"
   425     apply (rule prod_cong)
   425     apply (rule prod_cong)
   426     apply auto
   426     apply auto
   427     done
   427     done
   428   also have "\<dots> = fact (p - 1) mod p"
   428   also have "\<dots> = fact (p - 1) mod p"
   429     apply (subst fact_altdef_nat)
   429     apply (simp add: fact_setprod)
   430     apply (insert assms)
   430     apply (insert assms)
   431     apply (subst res_prime_units_eq)
   431     apply (subst res_prime_units_eq)
   432     apply (simp add: int_setprod zmod_int setprod_int_eq)
   432     apply (simp add: int_setprod zmod_int setprod_int_eq)
   433     done
   433     done
   434   finally have "fact (p - 1) mod p = \<ominus> \<one>" .
   434   finally have "fact (p - 1) mod p = \<ominus> \<one>" .
   441   assumes "prime p"
   441   assumes "prime p"
   442   shows "[fact (p - 1) = - 1] (mod p)"
   442   shows "[fact (p - 1) = - 1] (mod p)"
   443 proof (cases "p = 2")
   443 proof (cases "p = 2")
   444   case True
   444   case True
   445   then show ?thesis
   445   then show ?thesis
   446     by (simp add: cong_int_def fact_altdef_nat)
   446     by (simp add: cong_int_def fact_setprod)
   447 next
   447 next
   448   case False
   448   case False
   449   then show ?thesis
   449   then show ?thesis
   450     using assms prime_ge_2_nat
   450     using assms prime_ge_2_nat
   451     by (metis residues_prime.wilson_theorem1 residues_prime.intro le_eq_less_or_eq)
   451     by (metis residues_prime.wilson_theorem1 residues_prime.intro le_eq_less_or_eq)