src/HOL/NumberTheory/WilsonRuss.thy
changeset 30042 31039ee583fa
parent 23894 1a4167d761ac
equal deleted inserted replaced
30035:7f4d475a6c50 30042:31039ee583fa
    66      apply (unfold zcong_def, auto)
    66      apply (unfold zcong_def, auto)
    67   apply (subgoal_tac "\<not> p dvd 1")
    67   apply (subgoal_tac "\<not> p dvd 1")
    68    apply (rule_tac [2] zdvd_not_zless)
    68    apply (rule_tac [2] zdvd_not_zless)
    69     apply (subgoal_tac "p dvd 1")
    69     apply (subgoal_tac "p dvd 1")
    70      prefer 2
    70      prefer 2
    71      apply (subst zdvd_zminus_iff [symmetric], auto)
    71      apply (subst dvd_minus_iff [symmetric], auto)
    72   done
    72   done
    73 
    73 
    74 lemma inv_not_1:
    74 lemma inv_not_1:
    75     "zprime p \<Longrightarrow> 1 < a \<Longrightarrow> a < p - 1 ==> inv p a \<noteq> 1"
    75     "zprime p \<Longrightarrow> 1 < a \<Longrightarrow> a < p - 1 ==> inv p a \<noteq> 1"
    76   apply safe
    76   apply safe
    85     "[a * (p - 1) = 1] (mod p) = [a = p - 1] (mod p)"
    85     "[a * (p - 1) = 1] (mod p) = [a = p - 1] (mod p)"
    86   apply (unfold zcong_def)
    86   apply (unfold zcong_def)
    87   apply (simp add: OrderedGroup.diff_diff_eq diff_diff_eq2 zdiff_zmult_distrib2)
    87   apply (simp add: OrderedGroup.diff_diff_eq diff_diff_eq2 zdiff_zmult_distrib2)
    88   apply (rule_tac s = "p dvd -((a + 1) + (p * -a))" in trans)
    88   apply (rule_tac s = "p dvd -((a + 1) + (p * -a))" in trans)
    89    apply (simp add: mult_commute)
    89    apply (simp add: mult_commute)
    90   apply (subst zdvd_zminus_iff)
    90   apply (subst dvd_minus_iff)
    91   apply (subst zdvd_reduce)
    91   apply (subst zdvd_reduce)
    92   apply (rule_tac s = "p dvd (a + 1) + (p * -1)" in trans)
    92   apply (rule_tac s = "p dvd (a + 1) + (p * -1)" in trans)
    93    apply (subst zdvd_reduce, auto)
    93    apply (subst zdvd_reduce, auto)
    94   done
    94   done
    95 
    95