equal
deleted
inserted
replaced
210 from mod_less_divisor[of n 1] n01 have onen: "1 mod n = 1" |
210 from mod_less_divisor[of n 1] n01 have onen: "1 mod n = 1" |
211 by simp |
211 by simp |
212 from lucas_coprime_lemma[OF n01(3) an1] cong_imp_coprime_nat an1 |
212 from lucas_coprime_lemma[OF n01(3) an1] cong_imp_coprime_nat an1 |
213 have an: "coprime a n" "coprime (a ^ (n - 1)) n" |
213 have an: "coprime a n" "coprime (a ^ (n - 1)) n" |
214 using \<open>n \<ge> 2\<close> by simp_all |
214 using \<open>n \<ge> 2\<close> by simp_all |
215 have False if H0: "\<exists>m. 0 < m \<and> m < n - 1 \<and> [a ^ m = 1] (mod n)" (is "EX m. ?P m") |
215 have False if H0: "\<exists>m. 0 < m \<and> m < n - 1 \<and> [a ^ m = 1] (mod n)" (is "\<exists>m. ?P m") |
216 proof - |
216 proof - |
217 from H0[unfolded nat_exists_least_iff[of ?P]] obtain m where |
217 from H0[unfolded nat_exists_least_iff[of ?P]] obtain m where |
218 m: "0 < m" "m < n - 1" "[a ^ m = 1] (mod n)" "\<forall>k <m. \<not>?P k" |
218 m: "0 < m" "m < n - 1" "[a ^ m = 1] (mod n)" "\<forall>k <m. \<not>?P k" |
219 by blast |
219 by blast |
220 have False if nm1: "(n - 1) mod m > 0" |
220 have False if nm1: "(n - 1) mod m > 0" |