src/HOL/Number_Theory/Pocklington.thy
changeset 67091 1393c2340eec
parent 67051 e7e54a0b9197
child 67345 debef21cbed6
equal deleted inserted replaced
67090:0ec94bb9cec4 67091:1393c2340eec
   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"