# HG changeset patch
# User paulson
# Date 1046261767 -3600
# Node ID f8dcb1d9ea6890ef3ca90b2558576bc1179da13c
# Parent  e7649436869c8a474af7a785b80733f78477307a
zprime_def fixes by Jeremy Avigad

diff -r e7649436869c -r f8dcb1d9ea68 src/HOL/NumberTheory/EulerFermat.thy
--- a/src/HOL/NumberTheory/EulerFermat.thy	Wed Feb 26 10:48:00 2003 +0100
+++ b/src/HOL/NumberTheory/EulerFermat.thy	Wed Feb 26 13:16:07 2003 +0100
@@ -2,6 +2,9 @@
     ID:         $Id$
     Author:     Thomas M. Rasmussen
     Copyright   2000  University of Cambridge
+
+Changes by Jeremy Avigad, 2003/02/21:
+   repaired proof of Bnor_prime (removed use of zprime_def)
 *)
 
 header {* Fermat's Little Theorem extended to Euler's Totient function *}
@@ -57,8 +60,7 @@
 
 lemma abs_eq_1_iff [iff]: "(abs z = (1::int)) = (z = 1 \<or> z = -1)"
   -- {* LCP: not sure why this lemma is needed now *}
-  apply (auto simp add: zabs_def)
-  done
+by (auto simp add: zabs_def)
 
 
 text {* \medskip @{text norRRset} *}
@@ -73,11 +75,9 @@
 proof -
   case rule_context
   show ?thesis
-    apply (rule BnorRset.induct)
-    apply safe
+    apply (rule BnorRset.induct, safe)
      apply (case_tac [2] "0 < a")
-      apply (rule_tac [2] rule_context)
-       apply simp_all
+      apply (rule_tac [2] rule_context, simp_all)
      apply (simp_all add: BnorRset.simps rule_context)
   done
 qed
@@ -86,26 +86,22 @@
   apply (induct a m rule: BnorRset_induct)
    prefer 2
    apply (subst BnorRset.simps)
-   apply (unfold Let_def)
-   apply auto
+   apply (unfold Let_def, auto)
   done
 
 lemma Bnor_mem_zle_swap: "a < b ==> b \<notin> BnorRset (a, m)"
-  apply (auto dest: Bnor_mem_zle)
-  done
+by (auto dest: Bnor_mem_zle)
 
 lemma Bnor_mem_zg [rule_format]: "b \<in> BnorRset (a, m) --> 0 < b"
   apply (induct a m rule: BnorRset_induct)
    prefer 2
    apply (subst BnorRset.simps)
-   apply (unfold Let_def)
-   apply auto
+   apply (unfold Let_def, auto)
   done
 
 lemma Bnor_mem_if [rule_format]:
     "zgcd (b, m) = 1 --> 0 < b --> b \<le> a --> b \<in> BnorRset (a, m)"
-  apply (induct a m rule: BnorRset.induct)
-  apply auto
+  apply (induct a m rule: BnorRset.induct, auto)
    apply (case_tac "a = b")
     prefer 2
     apply (simp add: order_less_le)
@@ -114,32 +110,27 @@
    apply (subst BnorRset.simps)
    defer
    apply (subst BnorRset.simps)
-   apply (unfold Let_def)
-   apply auto
+   apply (unfold Let_def, auto)
   done
 
 lemma Bnor_in_RsetR [rule_format]: "a < m --> BnorRset (a, m) \<in> RsetR m"
-  apply (induct a m rule: BnorRset_induct)
-   apply simp
+  apply (induct a m rule: BnorRset_induct, simp)
   apply (subst BnorRset.simps)
-  apply (unfold Let_def)
-  apply auto
+  apply (unfold Let_def, auto)
   apply (rule RsetR.insert)
     apply (rule_tac [3] allI)
     apply (rule_tac [3] impI)
     apply (rule_tac [3] zcong_not)
        apply (subgoal_tac [6] "a' \<le> a - 1")
         apply (rule_tac [7] Bnor_mem_zle)
-        apply (rule_tac [5] Bnor_mem_zg)
-        apply auto
+        apply (rule_tac [5] Bnor_mem_zg, auto)
   done
 
 lemma Bnor_fin: "finite (BnorRset (a, m))"
   apply (induct a m rule: BnorRset_induct)
    prefer 2
    apply (subst BnorRset.simps)
-   apply (unfold Let_def)
-   apply auto
+   apply (unfold Let_def, auto)
   done
 
 lemma norR_mem_unique_aux: "a \<le> b - 1 ==> a < (b::int)"
@@ -150,13 +141,11 @@
   "1 < m ==>
     zgcd (a, m) = 1 ==> \<exists>!b. [a = b] (mod m) \<and> b \<in> norRRset m"
   apply (unfold norRRset_def)
-  apply (cut_tac a = a and m = m in zcong_zless_unique)
-   apply auto
+  apply (cut_tac a = a and m = m in zcong_zless_unique, auto)
    apply (rule_tac [2] m = m in zcong_zless_imp_eq)
        apply (auto intro: Bnor_mem_zle Bnor_mem_zg zcong_trans
 	 order_less_imp_le norR_mem_unique_aux simp add: zcong_sym)
-  apply (rule_tac "x" = "b" in exI)
-  apply safe
+  apply (rule_tac "x" = b in exI, safe)
   apply (rule Bnor_mem_if)
     apply (case_tac [2] "b = 0")
      apply (auto intro: order_less_le [THEN iffD2])
@@ -175,17 +164,14 @@
 lemma RRset_gcd [rule_format]:
     "is_RRset A m ==> a \<in> A --> zgcd (a, m) = 1"
   apply (unfold is_RRset_def)
-  apply (rule RsetR.induct)
-    apply auto
+  apply (rule RsetR.induct, auto)
   done
 
 lemma RsetR_zmult_mono:
   "A \<in> RsetR m ==>
     0 < m ==> zgcd (x, m) = 1 ==> (\<lambda>a. a * x) ` A \<in> RsetR m"
-  apply (erule RsetR.induct)
-   apply simp_all
-  apply (rule RsetR.insert)
-    apply auto
+  apply (erule RsetR.induct, simp_all)
+  apply (rule RsetR.insert, auto)
    apply (blast intro: zgcd_zgcd_zmult)
   apply (simp add: zcong_cancel)
   done
@@ -205,8 +191,7 @@
   apply (auto simp add: card_nor_eq_noX)
   apply (unfold noXRRset_def norRRset_def)
   apply (rule RsetR_zmult_mono)
-    apply (rule Bnor_in_RsetR)
-    apply simp_all
+    apply (rule Bnor_in_RsetR, simp_all)
   done
 
 lemma aux_some:
@@ -214,17 +199,14 @@
     ==> zcong a (SOME b. [a = b] (mod m) \<and> b \<in> norRRset m) m \<and>
       (SOME b. [a = b] (mod m) \<and> b \<in> norRRset m) \<in> norRRset m"
   apply (rule norR_mem_unique [THEN ex1_implies_ex, THEN someI_ex])
-   apply (rule_tac [2] RRset_gcd)
-    apply simp_all
+   apply (rule_tac [2] RRset_gcd, simp_all)
   done
 
 lemma RRset2norRR_correct:
   "1 < m ==> is_RRset A m ==> a \<in> A ==>
     [a = RRset2norRR A m a] (mod m) \<and> RRset2norRR A m a \<in> norRRset m"
-  apply (unfold RRset2norRR_def)
-  apply simp
-  apply (rule aux_some)
-    apply simp_all
+  apply (unfold RRset2norRR_def, simp)
+  apply (rule aux_some, simp_all)
   done
 
 lemmas RRset2norRR_correct1 =
@@ -233,9 +215,7 @@
   RRset2norRR_correct [THEN conjunct2, standard]
 
 lemma RsetR_fin: "A \<in> RsetR m ==> finite A"
-  apply (erule RsetR.induct)
-   apply auto
-  done
+by (erule RsetR.induct, auto)
 
 lemma RRset_zcong_eq [rule_format]:
   "1 < m ==>
@@ -253,15 +233,13 @@
 
 lemma RRset2norRR_inj:
     "1 < m ==> is_RRset A m ==> inj_on (RRset2norRR A m) A"
-  apply (unfold RRset2norRR_def inj_on_def)
-  apply auto
+  apply (unfold RRset2norRR_def inj_on_def, auto)
   apply (subgoal_tac "\<exists>b. ([x = b] (mod m) \<and> b \<in> norRRset m) \<and>
       ([y = b] (mod m) \<and> b \<in> norRRset m)")
    apply (rule_tac [2] aux)
      apply (rule_tac [3] aux_some)
        apply (rule_tac [2] aux_some)
-         apply (rule RRset_zcong_eq)
-             apply auto
+         apply (rule RRset_zcong_eq, auto)
   apply (rule_tac b = b in zcong_trans)
    apply (simp_all add: zcong_sym)
   done
@@ -271,19 +249,15 @@
   apply (rule card_seteq)
     prefer 3
     apply (subst card_image)
-      apply (rule_tac [2] RRset2norRR_inj)
-       apply auto
-     apply (rule_tac [4] RRset2norRR_correct2)
-       apply auto
+      apply (rule_tac [2] RRset2norRR_inj, auto)
+     apply (rule_tac [4] RRset2norRR_correct2, auto)
     apply (unfold is_RRset_def phi_def norRRset_def)
     apply (auto simp add: RsetR_fin Bnor_fin)
   done
 
 
 lemma Bnor_prod_power_aux: "a \<notin> A ==> inj f ==> f a \<notin> f ` A"
-  apply (unfold inj_on_def)
-  apply auto
-  done
+by (unfold inj_on_def, auto)
 
 lemma Bnor_prod_power [rule_format]:
   "x \<noteq> 0 ==> a < m --> setprod ((\<lambda>a. a * x) ` BnorRset (a, m)) =
@@ -291,8 +265,7 @@
   apply (induct a m rule: BnorRset_induct)
    prefer 2
    apply (subst BnorRset.simps)
-   apply (unfold Let_def)
-   apply auto
+   apply (unfold Let_def, auto)
   apply (simp add: Bnor_fin Bnor_mem_zle_swap)
   apply (subst setprod_insert)
     apply (rule_tac [2] Bnor_prod_power_aux)
@@ -317,8 +290,7 @@
   apply (induct a m rule: BnorRset_induct)
    prefer 2
    apply (subst BnorRset.simps)
-   apply (unfold Let_def)
-   apply auto
+   apply (unfold Let_def, auto)
   apply (simp add: Bnor_fin Bnor_mem_zle_swap)
   apply (blast intro: zgcd_zgcd_zmult)
   done
@@ -333,13 +305,11 @@
        in zcong_cancel2)
       prefer 5
       apply (subst Bnor_prod_power [symmetric])
-        apply (rule_tac [7] Bnor_prod_zgcd)
-        apply simp_all
+        apply (rule_tac [7] Bnor_prod_zgcd, simp_all)
   apply (rule bijzcong_zcong_prod)
   apply (fold norRRset_def noXRRset_def)
   apply (subst RRset2norRR_eq_norR [symmetric])
-    apply (rule_tac [3] inj_func_bijR)
-      apply auto
+    apply (rule_tac [3] inj_func_bijR, auto)
      apply (unfold zcongm_def)
      apply (rule_tac [2] RRset2norRR_correct1)
        apply (rule_tac [5] RRset2norRR_inj)
@@ -354,19 +324,21 @@
   "p \<in> zprime ==>
     a < p --> (\<forall>b. 0 < b \<and> b \<le> a --> zgcd (b, p) = 1)
     --> card (BnorRset (a, p)) = nat a"
-  apply (unfold zprime_def)
+  apply (auto simp add: zless_zprime_imp_zrelprime)
   apply (induct a p rule: BnorRset.induct)
   apply (subst BnorRset.simps)
-  apply (unfold Let_def)
-  apply auto
+  apply (unfold Let_def, auto)
+  apply (subgoal_tac "finite (BnorRset (a - 1,m))")
+   apply (subgoal_tac "a ~: BnorRset (a - 1,m)")
+    apply (auto simp add: card_insert_disjoint Suc_nat_eq_nat_zadd1)
+   apply (frule Bnor_mem_zle, arith)
+  apply (frule Bnor_fin)
   done
 
 lemma phi_prime: "p \<in> zprime ==> phi p = nat (p - 1)"
   apply (unfold phi_def norRRset_def)
-  apply (rule Bnor_prime)
-    apply auto
-  apply (erule zless_zprime_imp_zrelprime)
-   apply simp_all
+  apply (rule Bnor_prime, auto)
+  apply (erule zless_zprime_imp_zrelprime, simp_all)
   done
 
 theorem Little_Fermat:
@@ -374,8 +346,7 @@
   apply (subst phi_prime [symmetric])
    apply (rule_tac [2] Euler_Fermat)
     apply (erule_tac [3] zprime_imp_zrelprime)
-    apply (unfold zprime_def)
-    apply auto
+    apply (unfold zprime_def, auto)
   done
 
 end
diff -r e7649436869c -r f8dcb1d9ea68 src/HOL/NumberTheory/IntPrimes.thy
--- a/src/HOL/NumberTheory/IntPrimes.thy	Wed Feb 26 10:48:00 2003 +0100
+++ b/src/HOL/NumberTheory/IntPrimes.thy	Wed Feb 26 13:16:07 2003 +0100
@@ -2,6 +2,11 @@
     ID:         $Id$
     Author:     Thomas M. Rasmussen
     Copyright   2000  University of Cambridge
+
+Changes by Jeremy Avigad, 2003/02/21:
+   Repaired definition of zprime_def, added "0 <= m &"
+   Added lemma zgcd_geq_zero
+   Repaired proof of zprime_imp_zrelprime
 *)
 
 header {* Divisibility and prime numbers (on integers) *}
@@ -21,43 +26,43 @@
 
 consts
   xzgcda :: "int * int * int * int * int * int * int * int => int * int * int"
-  xzgcd :: "int => int => int * int * int"
-  zprime :: "int set"
-  zcong :: "int => int => int => bool"    ("(1[_ = _] '(mod _'))")
 
 recdef xzgcda
   "measure ((\<lambda>(m, n, r', r, s', s, t', t). nat r)
     :: int * int * int * int *int * int * int * int => nat)"
   "xzgcda (m, n, r', r, s', s, t', t) =
-    (if r \<le> 0 then (r', s', t')
-     else xzgcda (m, n, r, r' mod r, s, s' - (r' div r) * s, t, t' - (r' div r) * t))"
+	(if r \<le> 0 then (r', s', t')
+	 else xzgcda (m, n, r, r' mod r, 
+		      s, s' - (r' div r) * s, 
+		      t, t' - (r' div r) * t))"
 
 constdefs
   zgcd :: "int * int => int"
   "zgcd == \<lambda>(x,y). int (gcd (nat (abs x), nat (abs y)))"
 
-defs
-  xzgcd_def: "xzgcd m n == xzgcda (m, n, m, n, 1, 0, 0, 1)"
-  zprime_def: "zprime == {p. 1 < p \<and> (\<forall>m. m dvd p --> m = 1 \<or> m = p)}"
-  zcong_def: "[a = b] (mod m) == m dvd (a - b)"
+  zprime :: "int set"
+  "zprime == {p. 1 < p \<and> (\<forall>m. 0 <= m & m dvd p --> m = 1 \<or> m = p)}"
+
+  xzgcd :: "int => int => int * int * int"
+  "xzgcd m n == xzgcda (m, n, m, n, 1, 0, 0, 1)"
+
+  zcong :: "int => int => int => bool"    ("(1[_ = _] '(mod _'))")
+  "[a = b] (mod m) == m dvd (a - b)"
 
 
 lemma zabs_eq_iff:
     "(abs (z::int) = w) = (z = w \<and> 0 <= z \<or> z = -w \<and> z < 0)"
-  apply (auto simp add: zabs_def)
-  done
+  by (auto simp add: zabs_def)
 
 
 text {* \medskip @{term gcd} lemmas *}
 
 lemma gcd_add1_eq: "gcd (m + k, k) = gcd (m + k, m)"
-  apply (simp add: gcd_commute)
-  done
+  by (simp add: gcd_commute)
 
 lemma gcd_diff2: "m \<le> n ==> gcd (n, n - m) = gcd (n, m)"
   apply (subgoal_tac "n = m + (n - m)")
-   apply (erule ssubst, rule gcd_add1_eq)
-  apply simp
+   apply (erule ssubst, rule gcd_add1_eq, simp)
   done
 
 
@@ -69,14 +74,10 @@
   done
 
 lemma zdvd_0_left [iff]: "(0 dvd (m::int)) = (m = 0)"
-  apply (unfold dvd_def)
-  apply auto
-  done
+  by (unfold dvd_def, auto)
 
 lemma zdvd_1_left [iff]: "1 dvd (m::int)"
-  apply (unfold dvd_def)
-  apply simp
-  done
+  by (unfold dvd_def, simp)
 
 lemma zdvd_refl [simp]: "m dvd (m::int)"
   apply (unfold dvd_def)
@@ -89,23 +90,18 @@
   done
 
 lemma zdvd_zminus_iff: "(m dvd -n) = (m dvd (n::int))"
-  apply (unfold dvd_def)
-  apply auto
-   apply (rule_tac [!] x = "-k" in exI)
-  apply auto
+  apply (unfold dvd_def, auto)
+   apply (rule_tac [!] x = "-k" in exI, auto)
   done
 
 lemma zdvd_zminus2_iff: "(-m dvd n) = (m dvd (n::int))"
-  apply (unfold dvd_def)
-  apply auto
-   apply (rule_tac [!] x = "-k" in exI)
-  apply auto
+  apply (unfold dvd_def, auto)
+   apply (rule_tac [!] x = "-k" in exI, auto)
   done
 
 lemma zdvd_anti_sym:
     "0 < m ==> 0 < n ==> m dvd n ==> n dvd m ==> m = (n::int)"
-  apply (unfold dvd_def)
-  apply auto
+  apply (unfold dvd_def, auto)
   apply (simp add: zmult_assoc zmult_eq_self_iff int_0_less_mult_iff zmult_eq_1_iff)
   done
 
@@ -122,8 +118,7 @@
 lemma zdvd_zdiffD: "k dvd m - n ==> k dvd n ==> k dvd (m::int)"
   apply (subgoal_tac "m = n + (m - n)")
    apply (erule ssubst)
-   apply (blast intro: zdvd_zadd)
-  apply simp
+   apply (blast intro: zdvd_zadd, simp)
   done
 
 lemma zdvd_zmult: "k dvd (n::int) ==> k dvd m * n"
@@ -148,19 +143,16 @@
 
 lemma zdvd_zmultD2: "j * k dvd n ==> j dvd (n::int)"
   apply (unfold dvd_def)
-  apply (simp add: zmult_assoc)
-  apply blast
+  apply (simp add: zmult_assoc, blast)
   done
 
 lemma zdvd_zmultD: "j * k dvd n ==> k dvd (n::int)"
   apply (rule zdvd_zmultD2)
-  apply (subst zmult_commute)
-  apply assumption
+  apply (subst zmult_commute, assumption)
   done
 
 lemma zdvd_zmult_mono: "i dvd m ==> j dvd (n::int) ==> i * j dvd m * n"
-  apply (unfold dvd_def)
-  apply clarify
+  apply (unfold dvd_def, clarify)
   apply (rule_tac x = "k * ka" in exI)
   apply (simp add: zmult_ac)
   done
@@ -170,8 +162,7 @@
    apply (erule_tac [2] zdvd_zadd)
    apply (subgoal_tac "n = (n + k * m) - k * m")
     apply (erule ssubst)
-    apply (erule zdvd_zdiff)
-    apply simp_all
+    apply (erule zdvd_zdiff, simp_all)
   done
 
 lemma zdvd_zmod: "f dvd m ==> f dvd (n::int) ==> f dvd m mod n"
@@ -186,20 +177,16 @@
   done
 
 lemma zdvd_iff_zmod_eq_0: "(k dvd n) = (n mod (k::int) = 0)"
-  apply (unfold dvd_def)
-  apply auto
-  done
+  by (unfold dvd_def, auto)
 
 lemma zdvd_not_zless: "0 < m ==> m < n ==> \<not> n dvd (m::int)"
-  apply (unfold dvd_def)
-  apply auto
+  apply (unfold dvd_def, auto)
   apply (subgoal_tac "0 < n")
    prefer 2
    apply (blast intro: zless_trans)
   apply (simp add: int_0_less_mult_iff)
   apply (subgoal_tac "n * k < n * 1")
-   apply (drule zmult_zless_cancel1 [THEN iffD1])
-   apply auto
+   apply (drule zmult_zless_cancel1 [THEN iffD1], auto)
   done
 
 lemma int_dvd_iff: "(int m dvd z) = (m dvd nat (abs z))"
@@ -230,82 +217,67 @@
 
 lemma zminus_dvd_iff [iff]: "(-z dvd w) = (z dvd (w::int))"
   apply (auto simp add: dvd_def)
-   apply (rule_tac [!] x = "-k" in exI)
-   apply auto
+   apply (rule_tac [!] x = "-k" in exI, auto)
   done
 
 lemma dvd_zminus_iff [iff]: "(z dvd -w) = (z dvd (w::int))"
   apply (auto simp add: dvd_def)
    apply (drule zminus_equation [THEN iffD1])
-   apply (rule_tac [!] x = "-k" in exI)
-   apply auto
+   apply (rule_tac [!] x = "-k" in exI, auto)
   done
 
 
 subsection {* Euclid's Algorithm and GCD *}
 
 lemma zgcd_0 [simp]: "zgcd (m, 0) = abs m"
-  apply (simp add: zgcd_def zabs_def)
-  done
+  by (simp add: zgcd_def zabs_def)
 
 lemma zgcd_0_left [simp]: "zgcd (0, m) = abs m"
-  apply (simp add: zgcd_def zabs_def)
-  done
+  by (simp add: zgcd_def zabs_def)
 
 lemma zgcd_zminus [simp]: "zgcd (-m, n) = zgcd (m, n)"
-  apply (simp add: zgcd_def)
-  done
+  by (simp add: zgcd_def)
 
 lemma zgcd_zminus2 [simp]: "zgcd (m, -n) = zgcd (m, n)"
-  apply (simp add: zgcd_def)
-  done
+  by (simp add: zgcd_def)
 
 lemma zgcd_non_0: "0 < n ==> zgcd (m, n) = zgcd (n, m mod n)"
   apply (frule_tac b = n and a = m in pos_mod_sign)
-  apply (simp add: zgcd_def zabs_def nat_mod_distrib del:pos_mod_sign)
+  apply (simp del: pos_mod_sign add: zgcd_def zabs_def nat_mod_distrib)
   apply (auto simp add: gcd_non_0 nat_mod_distrib [symmetric] zmod_zminus1_eq_if)
   apply (frule_tac a = m in pos_mod_bound)
-  apply (simp add: nat_diff_distrib gcd_diff2 nat_le_eq_zle del:pos_mod_bound)
+  apply (simp del: pos_mod_bound add: nat_diff_distrib gcd_diff2 nat_le_eq_zle)
   done
 
 lemma zgcd_eq: "zgcd (m, n) = zgcd (n, m mod n)"
   apply (case_tac "n = 0", simp add: DIVISION_BY_ZERO)
   apply (auto simp add: linorder_neq_iff zgcd_non_0)
-  apply (cut_tac m = "-m" and n = "-n" in zgcd_non_0)
-   apply auto
+  apply (cut_tac m = "-m" and n = "-n" in zgcd_non_0, auto)
   done
 
 lemma zgcd_1 [simp]: "zgcd (m, 1) = 1"
-  apply (simp add: zgcd_def zabs_def)
-  done
+  by (simp add: zgcd_def zabs_def)
 
 lemma zgcd_0_1_iff [simp]: "(zgcd (0, m) = 1) = (abs m = 1)"
-  apply (simp add: zgcd_def zabs_def)
-  done
+  by (simp add: zgcd_def zabs_def)
 
 lemma zgcd_zdvd1 [iff]: "zgcd (m, n) dvd m"
-  apply (simp add: zgcd_def zabs_def int_dvd_iff)
-  done
+  by (simp add: zgcd_def zabs_def int_dvd_iff)
 
 lemma zgcd_zdvd2 [iff]: "zgcd (m, n) dvd n"
-  apply (simp add: zgcd_def zabs_def int_dvd_iff)
-  done
+  by (simp add: zgcd_def zabs_def int_dvd_iff)
 
 lemma zgcd_greatest_iff: "k dvd zgcd (m, n) = (k dvd m \<and> k dvd n)"
-  apply (simp add: zgcd_def zabs_def int_dvd_iff dvd_int_iff nat_dvd_iff)
-  done
+  by (simp add: zgcd_def zabs_def int_dvd_iff dvd_int_iff nat_dvd_iff)
 
 lemma zgcd_commute: "zgcd (m, n) = zgcd (n, m)"
-  apply (simp add: zgcd_def gcd_commute)
-  done
+  by (simp add: zgcd_def gcd_commute)
 
 lemma zgcd_1_left [simp]: "zgcd (1, m) = 1"
-  apply (simp add: zgcd_def gcd_1_left)
-  done
+  by (simp add: zgcd_def gcd_1_left)
 
 lemma zgcd_assoc: "zgcd (zgcd (k, m), n) = zgcd (k, zgcd (m, n))"
-  apply (simp add: zgcd_def gcd_assoc)
-  done
+  by (simp add: zgcd_def gcd_assoc)
 
 lemma zgcd_left_commute: "zgcd (k, zgcd (m, n)) = zgcd (m, zgcd (k, n))"
   apply (rule zgcd_commute [THEN trans])
@@ -317,31 +289,24 @@
   -- {* addition is an AC-operator *}
 
 lemma zgcd_zmult_distrib2: "0 \<le> k ==> k * zgcd (m, n) = zgcd (k * m, k * n)"
-  apply (simp del: zmult_zminus_right
-    add: zmult_zminus_right [symmetric] nat_mult_distrib zgcd_def zabs_def
-    zmult_less_0_iff gcd_mult_distrib2 [symmetric] zmult_int [symmetric])
-  done
+  by (simp del: zmult_zminus_right
+      add: zmult_zminus_right [symmetric] nat_mult_distrib zgcd_def zabs_def
+          zmult_less_0_iff gcd_mult_distrib2 [symmetric] zmult_int [symmetric])
 
 lemma zgcd_zmult_distrib2_abs: "zgcd (k * m, k * n) = abs k * zgcd (m, n)"
-  apply (simp add: zabs_def zgcd_zmult_distrib2)
-  done
+  by (simp add: zabs_def zgcd_zmult_distrib2)
 
 lemma zgcd_self [simp]: "0 \<le> m ==> zgcd (m, m) = m"
-  apply (cut_tac k = m and m = "1" and n = "1" in zgcd_zmult_distrib2)
-   apply simp_all
-  done
+  by (cut_tac k = m and m = 1 and n = 1 in zgcd_zmult_distrib2, simp_all)
 
 lemma zgcd_zmult_eq_self [simp]: "0 \<le> k ==> zgcd (k, k * n) = k"
-  apply (cut_tac k = k and m = "1" and n = n in zgcd_zmult_distrib2)
-   apply simp_all
-  done
+  by (cut_tac k = k and m = 1 and n = n in zgcd_zmult_distrib2, simp_all)
 
 lemma zgcd_zmult_eq_self2 [simp]: "0 \<le> k ==> zgcd (k * n, k) = k"
-  apply (cut_tac k = k and m = n and n = "1" in zgcd_zmult_distrib2)
-   apply simp_all
-  done
+  by (cut_tac k = k and m = n and n = 1 in zgcd_zmult_distrib2, simp_all)
 
-lemma zrelprime_zdvd_zmult_aux: "zgcd (n, k) = 1 ==> k dvd m * n ==> 0 \<le> m ==> k dvd m"
+lemma zrelprime_zdvd_zmult_aux:
+     "zgcd (n, k) = 1 ==> k dvd m * n ==> 0 \<le> m ==> k dvd m"
   apply (subgoal_tac "m = zgcd (m * n, m * k)")
    apply (erule ssubst, rule zgcd_greatest_iff [THEN iffD2])
    apply (simp_all add: zgcd_zmult_distrib2 [symmetric] int_0_le_mult_iff)
@@ -351,29 +316,31 @@
   apply (case_tac "0 \<le> m")
    apply (blast intro: zrelprime_zdvd_zmult_aux)
   apply (subgoal_tac "k dvd -m")
-   apply (rule_tac [2] zrelprime_zdvd_zmult_aux)
-     apply auto
+   apply (rule_tac [2] zrelprime_zdvd_zmult_aux, auto)
   done
 
+lemma zgcd_geq_zero: "0 <= zgcd(x,y)"
+  by (auto simp add: zgcd_def)
+
 lemma zprime_imp_zrelprime:
     "p \<in> zprime ==> \<not> p dvd n ==> zgcd (n, p) = 1"
-  apply (unfold zprime_def)
-  apply auto
+  apply (auto simp add: zprime_def)
+  apply (drule_tac x = "zgcd(n, p)" in allE)
+  apply (auto simp add: zgcd_zdvd2 [of n p] zgcd_geq_zero)
+  apply (insert zgcd_zdvd1 [of n p], auto)
   done
 
 lemma zless_zprime_imp_zrelprime:
     "p \<in> zprime ==> 0 < n ==> n < p ==> zgcd (n, p) = 1"
   apply (erule zprime_imp_zrelprime)
-  apply (erule zdvd_not_zless)
-  apply assumption
+  apply (erule zdvd_not_zless, assumption)
   done
 
 lemma zprime_zdvd_zmult:
     "0 \<le> (m::int) ==> p \<in> zprime ==> p dvd m * n ==> p dvd m \<or> p dvd n"
   apply safe
   apply (rule zrelprime_zdvd_zmult)
-   apply (rule zprime_imp_zrelprime)
-    apply auto
+   apply (rule zprime_imp_zrelprime, auto)
   done
 
 lemma zgcd_zadd_zmult [simp]: "zgcd (m + n * k, n) = zgcd (m, n)"
@@ -399,63 +366,50 @@
   done
 
 lemma zgcd_zmult_cancel: "zgcd (k, n) = 1 ==> zgcd (k * m, n) = zgcd (m, n)"
-  apply (simp add: zgcd_def nat_abs_mult_distrib gcd_mult_cancel)
-  done
+  by (simp add: zgcd_def nat_abs_mult_distrib gcd_mult_cancel)
 
 lemma zgcd_zgcd_zmult:
     "zgcd (k, m) = 1 ==> zgcd (n, m) = 1 ==> zgcd (k * n, m) = 1"
-  apply (simp (no_asm_simp) add: zgcd_zmult_cancel)
-  done
+  by (simp add: zgcd_zmult_cancel)
 
 lemma zdvd_iff_zgcd: "0 < m ==> (m dvd n) = (zgcd (n, m) = m)"
   apply safe
    apply (rule_tac [2] n = "zgcd (n, m)" in zdvd_trans)
-    apply (rule_tac [3] zgcd_zdvd1)
-   apply simp_all
-  apply (unfold dvd_def)
-  apply auto
+    apply (rule_tac [3] zgcd_zdvd1, simp_all)
+  apply (unfold dvd_def, auto)
   done
 
 
 subsection {* Congruences *}
 
 lemma zcong_1 [simp]: "[a = b] (mod 1)"
-  apply (unfold zcong_def)
-  apply auto
-  done
+  by (unfold zcong_def, auto)
 
 lemma zcong_refl [simp]: "[k = k] (mod m)"
-  apply (unfold zcong_def)
-  apply auto
-  done
+  by (unfold zcong_def, auto)
 
 lemma zcong_sym: "[a = b] (mod m) = [b = a] (mod m)"
-  apply (unfold zcong_def dvd_def)
-  apply auto
-   apply (rule_tac [!] x = "-k" in exI)
-   apply auto
+  apply (unfold zcong_def dvd_def, auto)
+   apply (rule_tac [!] x = "-k" in exI, auto)
   done
 
 lemma zcong_zadd:
     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a + c = b + d] (mod m)"
   apply (unfold zcong_def)
   apply (rule_tac s = "(a - b) + (c - d)" in subst)
-   apply (rule_tac [2] zdvd_zadd)
-    apply auto
+   apply (rule_tac [2] zdvd_zadd, auto)
   done
 
 lemma zcong_zdiff:
     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a - c = b - d] (mod m)"
   apply (unfold zcong_def)
   apply (rule_tac s = "(a - b) - (c - d)" in subst)
-   apply (rule_tac [2] zdvd_zdiff)
-    apply auto
+   apply (rule_tac [2] zdvd_zdiff, auto)
   done
 
 lemma zcong_trans:
     "[a = b] (mod m) ==> [b = c] (mod m) ==> [a = c] (mod m)"
-  apply (unfold zcong_def dvd_def)
-  apply auto
+  apply (unfold zcong_def dvd_def, auto)
   apply (rule_tac x = "k + ka" in exI)
   apply (simp add: zadd_ac zadd_zmult_distrib2)
   done
@@ -474,23 +428,18 @@
   done
 
 lemma zcong_scalar: "[a = b] (mod m) ==> [a * k = b * k] (mod m)"
-  apply (rule zcong_zmult)
-  apply simp_all
-  done
+  by (rule zcong_zmult, simp_all)
 
 lemma zcong_scalar2: "[a = b] (mod m) ==> [k * a = k * b] (mod m)"
-  apply (rule zcong_zmult)
-  apply simp_all
-  done
+  by (rule zcong_zmult, simp_all)
 
 lemma zcong_zmult_self: "[a * m = b * m] (mod m)"
   apply (unfold zcong_def)
-  apply (rule zdvd_zdiff)
-   apply simp_all
+  apply (rule zdvd_zdiff, simp_all)
   done
 
 lemma zcong_square:
-  "p \<in> zprime ==> 0 < a ==> [a * a = 1] (mod p)
+   "[|p \<in> zprime;  0 < a;  [a * a = 1] (mod p)|]
     ==> [a = 1] (mod p) \<or> [a = p - 1] (mod p)"
   apply (unfold zcong_def)
   apply (rule zprime_zdvd_zmult)
@@ -514,21 +463,18 @@
      apply (simp_all add: zdiff_zmult_distrib)
   apply (subgoal_tac "m dvd (-(a * k - b * k))")
    apply (simp add: zminus_zdiff_eq)
-  apply (subst zdvd_zminus_iff)
-  apply assumption
+  apply (subst zdvd_zminus_iff, assumption)
   done
 
 lemma zcong_cancel2:
   "0 \<le> m ==>
     zgcd (k, m) = 1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
-  apply (simp add: zmult_commute zcong_cancel)
-  done
+  by (simp add: zmult_commute zcong_cancel)
 
 lemma zcong_zgcd_zmult_zmod:
   "[a = b] (mod m) ==> [a = b] (mod n) ==> zgcd (m, n) = 1
     ==> [a = b] (mod m * n)"
-  apply (unfold zcong_def dvd_def)
-  apply auto
+  apply (unfold zcong_def dvd_def, auto)
   apply (subgoal_tac "m dvd n * ka")
    apply (subgoal_tac "m dvd ka")
     apply (case_tac [2] "0 \<le> ka")
@@ -547,17 +493,13 @@
 lemma zcong_zless_imp_eq:
   "0 \<le> a ==>
     a < m ==> 0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
-  apply (unfold zcong_def dvd_def)
-  apply auto
+  apply (unfold zcong_def dvd_def, auto)
   apply (drule_tac f = "\<lambda>z. z mod m" in arg_cong)
-  apply (cut_tac z = a and w = b in zless_linear)
-  apply auto
+  apply (cut_tac z = a and w = b in zless_linear, auto)
    apply (subgoal_tac [2] "(a - b) mod m = a - b")
-    apply (rule_tac [3] mod_pos_pos_trivial)
-     apply auto
+    apply (rule_tac [3] mod_pos_pos_trivial, auto)
   apply (subgoal_tac "(m + (a - b)) mod m = m + (a - b)")
-   apply (rule_tac [2] mod_pos_pos_trivial)
-    apply auto
+   apply (rule_tac [2] mod_pos_pos_trivial, auto)
   done
 
 lemma zcong_square_zless:
@@ -571,14 +513,12 @@
 lemma zcong_not:
     "0 < a ==> a < m ==> 0 < b ==> b < a ==> \<not> [a = b] (mod m)"
   apply (unfold zcong_def)
-  apply (rule zdvd_not_zless)
-   apply auto
+  apply (rule zdvd_not_zless, auto)
   done
 
 lemma zcong_zless_0:
     "0 \<le> a ==> a < m ==> [a = 0] (mod m) ==> a = 0"
-  apply (unfold zcong_def dvd_def)
-  apply auto
+  apply (unfold zcong_def dvd_def, auto)
   apply (subgoal_tac "0 < m")
    apply (simp add: int_0_le_mult_iff)
    apply (subgoal_tac "m * k < m * 1")
@@ -595,32 +535,29 @@
       apply (auto intro: zcong_trans zcong_zless_0 zcong_zless_imp_eq order_less_le
         simp add: zcong_sym)
   apply (unfold zcong_def dvd_def)
-  apply (rule_tac x = "a mod m" in exI)
-  apply (auto)
+  apply (rule_tac x = "a mod m" in exI, auto)
   apply (rule_tac x = "-(a div m)" in exI)
   apply (simp add:zdiff_eq_eq eq_zdiff_eq zadd_commute)
   done
 
 lemma zcong_iff_lin: "([a = b] (mod m)) = (\<exists>k. b = a + m * k)"
-  apply (unfold zcong_def dvd_def)
-  apply auto
-   apply (rule_tac [!] x = "-k" in exI)
-   apply auto
+  apply (unfold zcong_def dvd_def, auto)
+   apply (rule_tac [!] x = "-k" in exI, auto)
   done
 
 lemma zgcd_zcong_zgcd:
   "0 < m ==>
     zgcd (a, m) = 1 ==> [a = b] (mod m) ==> zgcd (b, m) = 1"
-  apply (auto simp add: zcong_iff_lin)
-  done
+  by (auto simp add: zcong_iff_lin)
 
-lemma zcong_zmod_aux: "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
-by(simp add: zdiff_zmult_distrib2 zadd_zdiff_eq eq_zdiff_eq zadd_ac)
+lemma zcong_zmod_aux:
+     "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
+  by(simp add: zdiff_zmult_distrib2 zadd_zdiff_eq eq_zdiff_eq zadd_ac)
 
 lemma zcong_zmod: "[a = b] (mod m) = [a mod m = b mod m] (mod m)"
   apply (unfold zcong_def)
   apply (rule_tac t = "a - b" in ssubst)
-  apply (rule_tac "m" = "m" in zcong_zmod_aux)
+  apply (rule_tac "m" = m in zcong_zmod_aux)
   apply (rule trans)
    apply (rule_tac [2] k = m and m = "a div m - b div m" in zdvd_reduce)
   apply (simp add: zadd_commute)
@@ -630,21 +567,17 @@
   apply auto
    apply (rule_tac m = m in zcong_zless_imp_eq)
        prefer 5
-       apply (subst zcong_zmod [symmetric])
-       apply (simp_all)
+       apply (subst zcong_zmod [symmetric], simp_all)
   apply (unfold zcong_def dvd_def)
   apply (rule_tac x = "a div m - b div m" in exI)
-  apply (rule_tac m1 = m in zcong_zmod_aux [THEN trans])
-  apply auto
+  apply (rule_tac m1 = m in zcong_zmod_aux [THEN trans], auto)
   done
 
 lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
-  apply (auto simp add: zcong_def)
-  done
+  by (auto simp add: zcong_def)
 
 lemma zcong_zero [iff]: "[a = b] (mod 0) = (a = b)"
-  apply (auto simp add: zcong_def)
-  done
+  by (auto simp add: zcong_def)
 
 lemma "[a = b] (mod m) = (a mod m = b mod m)"
   apply (case_tac "m = 0", simp add: DIVISION_BY_ZERO)
@@ -654,8 +587,7 @@
   txt{*Remainding case: @{term "m<0"}*}
   apply (rule_tac t = m in zminus_zminus [THEN subst])
   apply (subst zcong_zminus)
-  apply (subst zcong_zmod_eq)
-   apply arith
+  apply (subst zcong_zmod_eq, arith)
   apply (frule neg_mod_bound [of _ a], frule neg_mod_bound [of _ b]) 
   apply (simp add: zmod_zminus2_eq_if del: neg_mod_bound)
   done
@@ -664,14 +596,12 @@
 
 lemma zmod_zdvd_zmod:
     "0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
-  apply (unfold dvd_def)
-  apply auto
+  apply (unfold dvd_def, auto)
   apply (subst zcong_zmod_eq [symmetric])
    prefer 2
    apply (subst zcong_iff_lin)
    apply (rule_tac x = "k * (a div (m * k))" in exI)
-   apply(simp add:zmult_assoc [symmetric])
-  apply assumption
+   apply (simp add:zmult_assoc [symmetric], assumption)
   done
 
 
@@ -685,16 +615,13 @@
   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
     z = s and aa = t' and ab = t in xzgcda.induct)
   apply (subst zgcd_eq)
-  apply (subst xzgcda.simps)
-  apply auto
+  apply (subst xzgcda.simps, auto)
   apply (case_tac "r' mod r = 0")
    prefer 2
-   apply (frule_tac a = "r'" in pos_mod_sign)
-   apply auto
+   apply (frule_tac a = "r'" in pos_mod_sign, auto)
   apply (rule exI)
   apply (rule exI)
-  apply (subst xzgcda.simps)
-  apply auto
+  apply (subst xzgcda.simps, auto)
   apply (simp add: zabs_def)
   done
 
@@ -708,11 +635,9 @@
   apply (auto simp add: linorder_not_le)
   apply (case_tac "r' mod r = 0")
    prefer 2
-   apply (frule_tac a = "r'" in pos_mod_sign)
-   apply auto
+   apply (frule_tac a = "r'" in pos_mod_sign, auto)
   apply (erule_tac P = "xzgcda ?u = ?v" in rev_mp)
-  apply (subst xzgcda.simps)
-  apply auto
+  apply (subst xzgcda.simps, auto)
   apply (simp add: zabs_def)
   done
 
@@ -721,8 +646,7 @@
   apply (unfold xzgcd_def)
   apply (rule iffI)
    apply (rule_tac [2] xzgcd_correct_aux2 [THEN mp, THEN mp])
-    apply (rule xzgcd_correct_aux1 [THEN mp, THEN mp])
-     apply auto
+    apply (rule xzgcd_correct_aux1 [THEN mp, THEN mp], auto)
   done
 
 
@@ -730,9 +654,8 @@
 
 lemma xzgcda_linear_aux1:
   "(a - r * b) * m + (c - r * d) * (n::int) =
-    (a * m + c * n) - r * (b * m + d * n)"
-  apply (simp add: zdiff_zmult_distrib zadd_zmult_distrib2 zmult_assoc)
-  done
+   (a * m + c * n) - r * (b * m + d * n)"
+  by (simp add: zdiff_zmult_distrib zadd_zmult_distrib2 zmult_assoc)
 
 lemma xzgcda_linear_aux2:
   "r' = s' * m + t' * n ==> r = s * m + t * n
@@ -754,37 +677,31 @@
   apply (simp (no_asm))
   apply (rule impI)+
   apply (case_tac "r' mod r = 0")
-   apply (simp add: xzgcda.simps)
-   apply clarify
+   apply (simp add: xzgcda.simps, clarify)
   apply (subgoal_tac "0 < r' mod r")
    apply (rule_tac [2] order_le_neq_implies_less)
    apply (rule_tac [2] pos_mod_sign)
     apply (cut_tac m = m and n = n and r' = r' and r = r and s' = s' and
-      s = s and t' = t' and t = t in xzgcda_linear_aux2)
-      apply auto
+      s = s and t' = t' and t = t in xzgcda_linear_aux2, auto)
   done
 
 lemma xzgcd_linear:
     "0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
   apply (unfold xzgcd_def)
-  apply (erule xzgcda_linear)
-    apply assumption
+  apply (erule xzgcda_linear, assumption)
    apply auto
   done
 
 lemma zgcd_ex_linear:
     "0 < n ==> zgcd (m, n) = k ==> (\<exists>s t. k = s * m + t * n)"
-  apply (simp add: xzgcd_correct)
-  apply safe
+  apply (simp add: xzgcd_correct, safe)
   apply (rule exI)+
-  apply (erule xzgcd_linear)
-  apply auto
+  apply (erule xzgcd_linear, auto)
   done
 
 lemma zcong_lineq_ex:
     "0 < n ==> zgcd (a, n) = 1 ==> \<exists>x. [a * x = 1] (mod n)"
-  apply (cut_tac m = a and n = n and k = "1" in zgcd_ex_linear)
-    apply safe
+  apply (cut_tac m = a and n = n and k = 1 in zgcd_ex_linear, safe)
   apply (rule_tac x = s in exI)
   apply (rule_tac b = "s * a + t * n" in zcong_trans)
    prefer 2
@@ -803,10 +720,8 @@
           apply (simp_all (no_asm_simp))
    prefer 2
    apply (simp add: zcong_sym)
-  apply (cut_tac a = a and n = n in zcong_lineq_ex)
-    apply auto
-  apply (rule_tac x = "x * b mod n" in exI)
-  apply safe
+  apply (cut_tac a = a and n = n in zcong_lineq_ex, auto)
+  apply (rule_tac x = "x * b mod n" in exI, safe)
     apply (simp_all (no_asm_simp))
   apply (subst zcong_zmod)
   apply (subst zmod_zmult1_eq [symmetric])
diff -r e7649436869c -r f8dcb1d9ea68 src/HOL/NumberTheory/WilsonRuss.thy
--- a/src/HOL/NumberTheory/WilsonRuss.thy	Wed Feb 26 10:48:00 2003 +0100
+++ b/src/HOL/NumberTheory/WilsonRuss.thy	Wed Feb 26 13:16:07 2003 +0100
@@ -2,6 +2,9 @@
     ID:         $Id$
     Author:     Thomas M. Rasmussen
     Copyright   2000  University of Cambridge
+
+Changes by Jeremy Avigad, 2003/02/21:
+    repaired proof of prime_g_5
 *)
 
 header {* Wilson's Theorem according to Russinoff *}
@@ -33,9 +36,7 @@
 text {* \medskip @{term [source] inv} *}
 
 lemma inv_is_inv_aux: "1 < m ==> Suc (nat (m - 2)) = nat (m - 1)"
-  apply (subst int_int_eq [symmetric])
-  apply auto
-  done
+by (subst int_int_eq [symmetric], auto)
 
 lemma inv_is_inv:
     "p \<in> zprime \<Longrightarrow> 0 < a \<Longrightarrow> a < p ==> [a * inv p a = 1] (mod p)"
@@ -47,35 +48,30 @@
   apply (subst inv_is_inv_aux)
    apply (erule_tac [2] Little_Fermat)
    apply (erule_tac [2] zdvd_not_zless)
-   apply (unfold zprime_def)
-   apply auto
+   apply (unfold zprime_def, auto)
   done
 
 lemma inv_distinct:
     "p \<in> zprime \<Longrightarrow> 1 < a \<Longrightarrow> a < p - 1 ==> a \<noteq> inv p a"
   apply safe
   apply (cut_tac a = a and p = p in zcong_square)
-     apply (cut_tac [3] a = a and p = p in inv_is_inv)
-        apply auto
+     apply (cut_tac [3] a = a and p = p in inv_is_inv, auto)
    apply (subgoal_tac "a = 1")
     apply (rule_tac [2] m = p in zcong_zless_imp_eq)
         apply (subgoal_tac [7] "a = p - 1")
-         apply (rule_tac [8] m = p in zcong_zless_imp_eq)
-             apply auto
+         apply (rule_tac [8] m = p in zcong_zless_imp_eq, auto)
   done
 
 lemma inv_not_0:
     "p \<in> zprime \<Longrightarrow> 1 < a \<Longrightarrow> a < p - 1 ==> inv p a \<noteq> 0"
   apply safe
   apply (cut_tac a = a and p = p in inv_is_inv)
-     apply (unfold zcong_def)
-     apply auto
+     apply (unfold zcong_def, auto)
   apply (subgoal_tac "\<not> p dvd 1")
    apply (rule_tac [2] zdvd_not_zless)
     apply (subgoal_tac "p dvd 1")
      prefer 2
-     apply (subst zdvd_zminus_iff [symmetric])
-     apply auto
+     apply (subst zdvd_zminus_iff [symmetric], auto)
   done
 
 lemma inv_not_1:
@@ -85,8 +81,7 @@
      prefer 4
      apply simp
      apply (subgoal_tac "a = 1")
-      apply (rule_tac [2] zcong_zless_imp_eq)
-          apply auto
+      apply (rule_tac [2] zcong_zless_imp_eq, auto)
   done
 
 lemma inv_not_p_minus_1_aux: "[a * (p - 1) = 1] (mod p) = [a = p - 1] (mod p)"
@@ -97,19 +92,16 @@
   apply (subst zdvd_zminus_iff)
   apply (subst zdvd_reduce)
   apply (rule_tac s = "p dvd (a + 1) + (p * -1)" in trans)
-   apply (subst zdvd_reduce)
-   apply auto
+   apply (subst zdvd_reduce, auto)
   done
 
 lemma inv_not_p_minus_1:
     "p \<in> zprime \<Longrightarrow> 1 < a \<Longrightarrow> a < p - 1 ==> inv p a \<noteq> p - 1"
   apply safe
-  apply (cut_tac a = a and p = p in inv_is_inv)
-     apply auto
+  apply (cut_tac a = a and p = p in inv_is_inv, auto)
   apply (simp add: inv_not_p_minus_1_aux)
   apply (subgoal_tac "a = p - 1")
-   apply (rule_tac [2] zcong_zless_imp_eq)
-       apply auto
+   apply (rule_tac [2] zcong_zless_imp_eq, auto)
   done
 
 lemma inv_g_1:
@@ -121,20 +113,16 @@
      apply (subst zle_add1_eq_le [symmetric])
      apply (subst order_less_le)
      apply (rule_tac [2] inv_not_0)
-       apply (rule_tac [5] inv_not_1)
-         apply auto
-  apply (unfold inv_def zprime_def)
-  apply (simp)
+       apply (rule_tac [5] inv_not_1, auto)
+  apply (unfold inv_def zprime_def, simp)
   done
 
 lemma inv_less_p_minus_1:
     "p \<in> zprime \<Longrightarrow> 1 < a \<Longrightarrow> a < p - 1 ==> inv p a < p - 1"
   apply (case_tac "inv p a < p")
    apply (subst order_less_le)
-   apply (simp add: inv_not_p_minus_1)
-  apply auto
-  apply (unfold inv_def zprime_def)
-  apply (simp)
+   apply (simp add: inv_not_p_minus_1, auto)
+  apply (unfold inv_def zprime_def, simp)
   done
 
 lemma inv_inv_aux: "5 \<le> p ==>
@@ -149,8 +137,7 @@
   apply (induct z)
    apply (auto simp add: zpower_zadd_distrib)
   apply (subgoal_tac "zcong (x^y * x^(y * n)) (1 * 1) p")
-   apply (rule_tac [2] zcong_zmult)
-    apply simp_all
+   apply (rule_tac [2] zcong_zmult, simp_all)
   done
 
 lemma inv_inv: "p \<in> zprime \<Longrightarrow>
@@ -169,8 +156,7 @@
         apply (rule_tac [3] zcong_zmult)
          apply (rule_tac [4] zcong_zpower_zmult)
          apply (erule_tac [4] Little_Fermat)
-         apply (rule_tac [4] zdvd_not_zless)
-          apply (simp_all)
+         apply (rule_tac [4] zdvd_not_zless, simp_all)
   done
 
 
@@ -186,11 +172,9 @@
 proof -
   case rule_context
   show ?thesis
-    apply (rule wset.induct)
-    apply safe
+    apply (rule wset.induct, safe)
      apply (case_tac [2] "1 < a")
-      apply (rule_tac [2] rule_context)
-        apply simp_all
+      apply (rule_tac [2] rule_context, simp_all)
       apply (simp_all add: wset.simps rule_context)
     done
 qed
@@ -199,55 +183,47 @@
   "1 < a \<Longrightarrow> b \<notin> wset (a - 1, p)
     ==> b \<in> wset (a, p) --> b = a \<or> b = inv p a"
   apply (subst wset.simps)
-  apply (unfold Let_def)
-  apply simp
+  apply (unfold Let_def, simp)
   done
 
 lemma wset_mem_mem [simp]: "1 < a ==> a \<in> wset (a, p)"
   apply (subst wset.simps)
-  apply (unfold Let_def)
-  apply simp
+  apply (unfold Let_def, simp)
   done
 
 lemma wset_subset: "1 < a \<Longrightarrow> b \<in> wset (a - 1, p) ==> b \<in> wset (a, p)"
   apply (subst wset.simps)
-  apply (unfold Let_def)
-  apply auto
+  apply (unfold Let_def, auto)
   done
 
 lemma wset_g_1 [rule_format]:
     "p \<in> zprime --> a < p - 1 --> b \<in> wset (a, p) --> 1 < b"
-  apply (induct a p rule: wset_induct)
-   apply auto
+  apply (induct a p rule: wset_induct, auto)
   apply (case_tac "b = a")
    apply (case_tac [2] "b = inv p a")
     apply (subgoal_tac [3] "b = a \<or> b = inv p a")
      apply (rule_tac [4] wset_mem_imp_or)
        prefer 2
        apply simp
-       apply (rule inv_g_1)
-         apply auto
+       apply (rule inv_g_1, auto)
   done
 
 lemma wset_less [rule_format]:
     "p \<in> zprime --> a < p - 1 --> b \<in> wset (a, p) --> b < p - 1"
-  apply (induct a p rule: wset_induct)
-   apply auto
+  apply (induct a p rule: wset_induct, auto)
   apply (case_tac "b = a")
    apply (case_tac [2] "b = inv p a")
     apply (subgoal_tac [3] "b = a \<or> b = inv p a")
      apply (rule_tac [4] wset_mem_imp_or)
        prefer 2
        apply simp
-       apply (rule inv_less_p_minus_1)
-         apply auto
+       apply (rule inv_less_p_minus_1, auto)
   done
 
 lemma wset_mem [rule_format]:
   "p \<in> zprime -->
     a < p - 1 --> 1 < b --> b \<le> a --> b \<in> wset (a, p)"
-  apply (induct a p rule: wset.induct)
-  apply auto
+  apply (induct a p rule: wset.induct, auto)
    apply (subgoal_tac "b = a")
     apply (rule_tac [2] zle_anti_sym)
      apply (rule_tac [4] wset_subset)
@@ -258,19 +234,16 @@
 lemma wset_mem_inv_mem [rule_format]:
   "p \<in> zprime --> 5 \<le> p --> a < p - 1 --> b \<in> wset (a, p)
     --> inv p b \<in> wset (a, p)"
-  apply (induct a p rule: wset_induct)
-   apply auto
+  apply (induct a p rule: wset_induct, auto)
    apply (case_tac "b = a")
     apply (subst wset.simps)
     apply (unfold Let_def)
-    apply (rule_tac [3] wset_subset)
-     apply auto
+    apply (rule_tac [3] wset_subset, auto)
   apply (case_tac "b = inv p a")
    apply (simp (no_asm_simp))
    apply (subst inv_inv)
        apply (subgoal_tac [6] "b = a \<or> b = inv p a")
-        apply (rule_tac [7] wset_mem_imp_or)
-          apply auto
+        apply (rule_tac [7] wset_mem_imp_or, auto)
   done
 
 lemma wset_inv_mem_mem:
@@ -278,16 +251,14 @@
     \<Longrightarrow> inv p b \<in> wset (a, p) \<Longrightarrow> b \<in> wset (a, p)"
   apply (rule_tac s = "inv p (inv p b)" and t = b in subst)
    apply (rule_tac [2] wset_mem_inv_mem)
-      apply (rule inv_inv)
-         apply simp_all
+      apply (rule inv_inv, simp_all)
   done
 
 lemma wset_fin: "finite (wset (a, p))"
   apply (induct a p rule: wset_induct)
    prefer 2
    apply (subst wset.simps)
-   apply (unfold Let_def)
-   apply auto
+   apply (unfold Let_def, auto)
   done
 
 lemma wset_zcong_prod_1 [rule_format]:
@@ -296,8 +267,7 @@
   apply (induct a p rule: wset_induct)
    prefer 2
    apply (subst wset.simps)
-   apply (unfold Let_def)
-   apply auto
+   apply (unfold Let_def, auto)
   apply (subst setprod_insert)
     apply (tactic {* stac (thm "setprod_insert") 3 *})
       apply (subgoal_tac [5]
@@ -310,8 +280,7 @@
          apply (subgoal_tac [4] "a \<in> wset (a - 1, p)")
           apply (rule_tac [5] wset_inv_mem_mem)
                apply (simp_all add: wset_fin)
-  apply (rule inv_distinct)
-    apply auto
+  apply (rule inv_distinct, auto)
   done
 
 lemma d22set_eq_wset: "p \<in> zprime ==> d22set (p - 2) = wset (p - 2, p)"
@@ -325,8 +294,7 @@
        apply (subst zle_add1_eq_le [symmetric])
        apply (subgoal_tac "p - 2 + 1 = p - 1")
         apply (simp (no_asm_simp))
-        apply (erule wset_less)
-         apply auto
+        apply (erule wset_less, auto)
   done
 
 
@@ -334,16 +302,14 @@
 
 lemma prime_g_5: "p \<in> zprime \<Longrightarrow> p \<noteq> 2 \<Longrightarrow> p \<noteq> 3 ==> 5 \<le> p"
   apply (unfold zprime_def dvd_def)
-  apply (case_tac "p = 4")
-   apply auto
+  apply (case_tac "p = 4", auto)
    apply (rule notE)
     prefer 2
     apply assumption
    apply (simp (no_asm))
-   apply (rule_tac x = "2" in exI)
-   apply safe
-     apply (rule_tac x = "2" in exI)
-     apply auto
+   apply (rule_tac x = 2 in exI)
+   apply (safe, arith)
+     apply (rule_tac x = 2 in exI, auto)
   done
 
 theorem Wilson_Russ:
@@ -352,8 +318,7 @@
    apply (rule_tac [2] zcong_zmult)
     apply (simp only: zprime_def)
     apply (subst zfact.simps)
-    apply (rule_tac t = "p - 1 - 1" and s = "p - 2" in subst)
-     apply auto
+    apply (rule_tac t = "p - 1 - 1" and s = "p - 2" in subst, auto)
    apply (simp only: zcong_def)
    apply (simp (no_asm_simp))
   apply (case_tac "p = 2")
@@ -364,8 +329,7 @@
    apply (erule_tac [2] prime_g_5)
     apply (subst d22set_prod_zfact [symmetric])
     apply (subst d22set_eq_wset)
-     apply (rule_tac [2] wset_zcong_prod_1)
-       apply auto
+     apply (rule_tac [2] wset_zcong_prod_1, auto)
   done
 
 end