src/HOL/NumberTheory/IntPrimes.thy

 
 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> Numeral0 then (r', s', 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))"
   (hints simp: pos_mod_bound)
 
 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, Numeral1, Numeral0, Numeral0, Numeral1)"
-  zprime_def: "zprime == {p. Numeral1 < p \<and> (\<forall>m. m dvd p --> m = Numeral1 \<or> m = p)}"
+  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)"
 
 
 lemma zabs_eq_iff:
-    "(abs (z::int) = w) = (z = w \<and> Numeral0 <= z \<or> z = -w \<and> z < Numeral0)"
+    "(abs (z::int) = w) = (z = w \<and> 0 <= z \<or> z = -w \<and> z < 0)"
   apply (auto simp add: zabs_def)
   done
 
 
 text {* \medskip @{term gcd} lemmas *}

   done
 
 
 subsection {* Divides relation *}
 
-lemma zdvd_0_right [iff]: "(m::int) dvd Numeral0"
+lemma zdvd_0_right [iff]: "(m::int) dvd 0"
   apply (unfold dvd_def)
   apply (blast intro: zmult_0_right [symmetric])
   done
 
-lemma zdvd_0_left [iff]: "(Numeral0 dvd (m::int)) = (m = Numeral0)"
-  apply (unfold dvd_def)
-  apply auto
-  done
-
-lemma zdvd_1_left [iff]: "Numeral1 dvd (m::int)"
+lemma zdvd_0_left [iff]: "(0 dvd (m::int)) = (m = 0)"
+  apply (unfold dvd_def)
+  apply auto
+  done
+
+lemma zdvd_1_left [iff]: "1 dvd (m::int)"
   apply (unfold dvd_def)
   apply simp
   done
 
 lemma zdvd_refl [simp]: "m dvd (m::int)"

    apply (rule_tac [!] x = "-k" in exI)
   apply auto
   done
 
 lemma zdvd_anti_sym:
-    "Numeral0 < m ==> Numeral0 < n ==> m dvd n ==> n dvd m ==> m = (n::int)"
+    "0 < m ==> 0 < n ==> m dvd n ==> n dvd m ==> m = (n::int)"
   apply (unfold dvd_def)
   apply auto
   apply (simp add: zmult_assoc zmult_eq_self_iff int_0_less_mult_iff zmult_eq_1_iff)
   done
 

   apply (subgoal_tac "k dvd n * (m div n) + m mod n")
    apply (simp add: zmod_zdiv_equality [symmetric])
   apply (simp add: zdvd_zadd zdvd_zmult2)
   done
 
-lemma zdvd_iff_zmod_eq_0: "(k dvd n) = (n mod (k::int) = Numeral0)"
-  apply (unfold dvd_def)
-  apply auto
-  done
-
-lemma zdvd_not_zless: "Numeral0 < m ==> m < n ==> \<not> n dvd (m::int)"
-  apply (unfold dvd_def)
-  apply auto
-  apply (subgoal_tac "Numeral0 < n")
+lemma zdvd_iff_zmod_eq_0: "(k dvd n) = (n mod (k::int) = 0)"
+  apply (unfold dvd_def)
+  apply auto
+  done
+
+lemma zdvd_not_zless: "0 < m ==> m < n ==> \<not> n dvd (m::int)"
+  apply (unfold dvd_def)
+  apply 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 * Numeral1")
+  apply (subgoal_tac "n * k < n * 1")
    apply (drule zmult_zless_cancel1 [THEN iffD1])
    apply auto
   done
 
 lemma int_dvd_iff: "(int m dvd z) = (m dvd nat (abs z))"

     apply (cut_tac k = m in int_less_0_conv)
     apply (auto simp add: int_0_le_mult_iff zmult_less_0_iff
       nat_mult_distrib [symmetric] nat_eq_iff2)
   done
 
-lemma nat_dvd_iff: "(nat z dvd m) = (if Numeral0 \<le> z then (z dvd int m) else m = 0)"
+lemma nat_dvd_iff: "(nat z dvd m) = (if 0 \<le> z then (z dvd int m) else m = 0)"
   apply (auto simp add: dvd_def zmult_int [symmetric])
   apply (rule_tac x = "nat k" in exI)
   apply (cut_tac k = m in int_less_0_conv)
   apply (auto simp add: int_0_le_mult_iff zmult_less_0_iff
     nat_mult_distrib [symmetric] nat_eq_iff2)

   done
 
 
 subsection {* Euclid's Algorithm and GCD *}
 
-lemma zgcd_0 [simp]: "zgcd (m, Numeral0) = abs m"
+lemma zgcd_0 [simp]: "zgcd (m, 0) = abs m"
   apply (simp add: zgcd_def zabs_def)
   done
 
-lemma zgcd_0_left [simp]: "zgcd (Numeral0, m) = abs m"
+lemma zgcd_0_left [simp]: "zgcd (0, m) = abs m"
   apply (simp add: zgcd_def zabs_def)
   done
 
 lemma zgcd_zminus [simp]: "zgcd (-m, n) = zgcd (m, n)"
   apply (simp add: zgcd_def)

 
 lemma zgcd_zminus2 [simp]: "zgcd (m, -n) = zgcd (m, n)"
   apply (simp add: zgcd_def)
   done
 
-lemma zgcd_non_0: "Numeral0 < n ==> zgcd (m, n) = zgcd (n, m mod n)"
+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)
   apply (cut_tac a = "-m" and b = n in zmod_zminus1_eq_if)
   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 (rule gcd_diff2)
   apply (simp add: nat_le_eq_zle)
   done
 
 lemma zgcd_eq: "zgcd (m, n) = zgcd (n, m mod n)"
-  apply (tactic {* zdiv_undefined_case_tac "n = Numeral0" 1 *})
+  apply (tactic {* zdiv_undefined_case_tac "n = 0" 1 *})
   apply (auto simp add: linorder_neq_iff zgcd_non_0)
   apply (cut_tac m = "-m" and n = "-n" in zgcd_non_0)
    apply auto
   done
 
-lemma zgcd_1 [simp]: "zgcd (m, Numeral1) = Numeral1"
+lemma zgcd_1 [simp]: "zgcd (m, 1) = 1"
   apply (simp add: zgcd_def zabs_def)
   done
 
-lemma zgcd_0_1_iff [simp]: "(zgcd (Numeral0, m) = Numeral1) = (abs m = Numeral1)"
+lemma zgcd_0_1_iff [simp]: "(zgcd (0, m) = 1) = (abs m = 1)"
   apply (simp add: zgcd_def zabs_def)
   done
 
 lemma zgcd_zdvd1 [iff]: "zgcd (m, n) dvd m"
   apply (simp add: zgcd_def zabs_def int_dvd_iff)

 
 lemma zgcd_commute: "zgcd (m, n) = zgcd (n, m)"
   apply (simp add: zgcd_def gcd_commute)
   done
 
-lemma zgcd_1_left [simp]: "zgcd (Numeral1, m) = Numeral1"
+lemma zgcd_1_left [simp]: "zgcd (1, m) = 1"
   apply (simp add: zgcd_def gcd_1_left)
   done
 
 lemma zgcd_assoc: "zgcd (zgcd (k, m), n) = zgcd (k, zgcd (m, n))"
   apply (simp add: zgcd_def gcd_assoc)

   done
 
 lemmas zgcd_ac = zgcd_assoc zgcd_commute zgcd_left_commute
   -- {* addition is an AC-operator *}
 
-lemma zgcd_zmult_distrib2: "Numeral0 \<le> k ==> k * zgcd (m, n) = zgcd (k * m, k * n)"
+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
 
 lemma zgcd_zmult_distrib2_abs: "zgcd (k * m, k * n) = abs k * zgcd (m, n)"
   apply (simp add: zabs_def zgcd_zmult_distrib2)
   done
 
-lemma zgcd_self [simp]: "Numeral0 \<le> m ==> zgcd (m, m) = m"
-  apply (cut_tac k = m and m = "Numeral1" and n = "Numeral1" in 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
 
-lemma zgcd_zmult_eq_self [simp]: "Numeral0 \<le> k ==> zgcd (k, k * n) = k"
-  apply (cut_tac k = k and m = "Numeral1" and n = n in zgcd_zmult_distrib2)
+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
 
-lemma zgcd_zmult_eq_self2 [simp]: "Numeral0 \<le> k ==> zgcd (k * n, k) = k"
-  apply (cut_tac k = k and m = n and n = "Numeral1" in zgcd_zmult_distrib2)
+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
 
-lemma aux: "zgcd (n, k) = Numeral1 ==> k dvd m * n ==> Numeral0 \<le> m ==> k dvd m"
+lemma 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)
   done
 
-lemma zrelprime_zdvd_zmult: "zgcd (n, k) = Numeral1 ==> k dvd m * n ==> k dvd m"
-  apply (case_tac "Numeral0 \<le> m")
+lemma zrelprime_zdvd_zmult: "zgcd (n, k) = 1 ==> k dvd m * n ==> k dvd m"
+  apply (case_tac "0 \<le> m")
    apply (blast intro: aux)
   apply (subgoal_tac "k dvd -m")
    apply (rule_tac [2] aux)
      apply auto
   done
 
 lemma zprime_imp_zrelprime:
-    "p \<in> zprime ==> \<not> p dvd n ==> zgcd (n, p) = Numeral1"
+    "p \<in> zprime ==> \<not> p dvd n ==> zgcd (n, p) = 1"
   apply (unfold zprime_def)
   apply auto
   done
 
 lemma zless_zprime_imp_zrelprime:
-    "p \<in> zprime ==> Numeral0 < n ==> n < p ==> zgcd (n, p) = Numeral1"
+    "p \<in> zprime ==> 0 < n ==> n < p ==> zgcd (n, p) = 1"
   apply (erule zprime_imp_zrelprime)
   apply (erule zdvd_not_zless)
   apply assumption
   done
 
 lemma zprime_zdvd_zmult:
-    "Numeral0 \<le> (m::int) ==> p \<in> zprime ==> p dvd m * n ==> p dvd m \<or> p dvd n"
+    "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
   done

   apply (simp add: zgcd_greatest_iff)
   apply (blast intro: zdvd_trans)
   done
 
 lemma zgcd_zmult_zdvd_zgcd:
-    "zgcd (k, n) = Numeral1 ==> zgcd (k * m, n) dvd zgcd (m, n)"
+    "zgcd (k, n) = 1 ==> zgcd (k * m, n) dvd zgcd (m, n)"
   apply (simp add: zgcd_greatest_iff)
   apply (rule_tac n = k in zrelprime_zdvd_zmult)
    prefer 2
    apply (simp add: zmult_commute)
   apply (subgoal_tac "zgcd (k, zgcd (k * m, n)) = zgcd (k * m, zgcd (k, n))")
    apply simp
   apply (simp (no_asm) add: zgcd_ac)
   done
 
-lemma zgcd_zmult_cancel: "zgcd (k, n) = Numeral1 ==> zgcd (k * m, n) = zgcd (m, n)"
+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
 
 lemma zgcd_zgcd_zmult:
-    "zgcd (k, m) = Numeral1 ==> zgcd (n, m) = Numeral1 ==> zgcd (k * n, m) = Numeral1"
+    "zgcd (k, m) = 1 ==> zgcd (n, m) = 1 ==> zgcd (k * n, m) = 1"
   apply (simp (no_asm_simp) add: zgcd_zmult_cancel)
   done
 
-lemma zdvd_iff_zgcd: "Numeral0 < m ==> (m dvd n) = (zgcd (n, m) = m)"
+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)

   done
 
 
 subsection {* Congruences *}
 
-lemma zcong_1 [simp]: "[a = b] (mod Numeral1)"
+lemma zcong_1 [simp]: "[a = b] (mod 1)"
   apply (unfold zcong_def)
   apply auto
   done
 
 lemma zcong_refl [simp]: "[k = k] (mod m)"

   apply (rule zdvd_zdiff)
    apply simp_all
   done
 
 lemma zcong_square:
-  "p \<in> zprime ==> Numeral0 < a ==> [a * a = Numeral1] (mod p)
-    ==> [a = Numeral1] (mod p) \<or> [a = p - Numeral1] (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)
-    apply (rule_tac [3] s = "a * a - Numeral1 + p * (Numeral1 - a)" in subst)
+    apply (rule_tac [3] s = "a * a - 1 + p * (1 - a)" in subst)
      prefer 4
      apply (simp add: zdvd_reduce)
     apply (simp_all add: zdiff_zmult_distrib zmult_commute zdiff_zmult_distrib2)
   done
 
 lemma zcong_cancel:
-  "Numeral0 \<le> m ==>
-    zgcd (k, m) = Numeral1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
+  "0 \<le> m ==>
+    zgcd (k, m) = 1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
   apply safe
    prefer 2
    apply (blast intro: zcong_scalar)
   apply (case_tac "b < a")
    prefer 2

   apply (subst zdvd_zminus_iff)
   apply assumption
   done
 
 lemma zcong_cancel2:
-  "Numeral0 \<le> m ==>
-    zgcd (k, m) = Numeral1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
+  "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
 
 lemma zcong_zgcd_zmult_zmod:
-  "[a = b] (mod m) ==> [a = b] (mod n) ==> zgcd (m, n) = Numeral1
+  "[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 (subgoal_tac "m dvd n * ka")
    apply (subgoal_tac "m dvd ka")
-    apply (case_tac [2] "Numeral0 \<le> ka")
+    apply (case_tac [2] "0 \<le> ka")
      prefer 3
      apply (subst zdvd_zminus_iff [symmetric])
      apply (rule_tac n = n in zrelprime_zdvd_zmult)
       apply (simp add: zgcd_commute)
      apply (simp add: zmult_commute zdvd_zminus_iff)

    apply (auto simp add: dvd_def)
   apply (blast intro: sym)
   done
 
 lemma zcong_zless_imp_eq:
-  "Numeral0 \<le> a ==>
-    a < m ==> Numeral0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
+  "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 (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 (rule_tac [2] mod_pos_pos_trivial)
     apply auto
   done
 
 lemma zcong_square_zless:
-  "p \<in> zprime ==> Numeral0 < a ==> a < p ==>
-    [a * a = Numeral1] (mod p) ==> a = Numeral1 \<or> a = p - Numeral1"
+  "p \<in> zprime ==> 0 < a ==> a < p ==>
+    [a * a = 1] (mod p) ==> a = 1 \<or> a = p - 1"
   apply (cut_tac p = p and a = a in zcong_square)
      apply (simp add: zprime_def)
     apply (auto intro: zcong_zless_imp_eq)
   done
 
 lemma zcong_not:
-    "Numeral0 < a ==> a < m ==> Numeral0 < b ==> b < a ==> \<not> [a = b] (mod m)"
+    "0 < a ==> a < m ==> 0 < b ==> b < a ==> \<not> [a = b] (mod m)"
   apply (unfold zcong_def)
   apply (rule zdvd_not_zless)
    apply auto
   done
 
 lemma zcong_zless_0:
-    "Numeral0 \<le> a ==> a < m ==> [a = Numeral0] (mod m) ==> a = Numeral0"
+    "0 \<le> a ==> a < m ==> [a = 0] (mod m) ==> a = 0"
   apply (unfold zcong_def dvd_def)
   apply auto
-  apply (subgoal_tac "Numeral0 < m")
+  apply (subgoal_tac "0 < m")
    apply (rotate_tac -1)
    apply (simp add: int_0_le_mult_iff)
-   apply (subgoal_tac "m * k < m * Numeral1")
+   apply (subgoal_tac "m * k < m * 1")
     apply (drule zmult_zless_cancel1 [THEN iffD1])
     apply (auto simp add: linorder_neq_iff)
   done
 
 lemma zcong_zless_unique:
-    "Numeral0 < m ==> (\<exists>!b. Numeral0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
+    "0 < m ==> (\<exists>!b. 0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
   apply auto
    apply (subgoal_tac [2] "[b = y] (mod m)")
-    apply (case_tac [2] "b = Numeral0")
-     apply (case_tac [3] "y = Numeral0")
+    apply (case_tac [2] "b = 0")
+     apply (case_tac [3] "y = 0")
       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 simp add: pos_mod_sign pos_mod_bound)

    apply (rule_tac [!] x = "-k" in exI)
    apply auto
   done
 
 lemma zgcd_zcong_zgcd:
-  "Numeral0 < m ==>
-    zgcd (a, m) = Numeral1 ==> [a = b] (mod m) ==> zgcd (b, m) = Numeral1"
+  "0 < m ==>
+    zgcd (a, m) = 1 ==> [a = b] (mod m) ==> zgcd (b, m) = 1"
   apply (auto simp add: zcong_iff_lin)
   done
 
 lemma aux: "a = c ==> b = d ==> a - b = c - (d::int)"
   apply auto

   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)
   done
 
-lemma zcong_zmod_eq: "Numeral0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
+lemma zcong_zmod_eq: "0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
   apply auto
    apply (rule_tac m = m in zcong_zless_imp_eq)
        prefer 5
        apply (subst zcong_zmod [symmetric])
        apply (simp_all add: pos_mod_bound pos_mod_sign)

 
 lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
   apply (auto simp add: zcong_def)
   done
 
-lemma zcong_zero [iff]: "[a = b] (mod Numeral0) = (a = b)"
+lemma zcong_zero [iff]: "[a = b] (mod 0) = (a = b)"
   apply (auto simp add: zcong_def)
   done
 
 lemma "[a = b] (mod m) = (a mod m = b mod m)"
-  apply (tactic {* zdiv_undefined_case_tac "m = Numeral0" 1 *})
-  apply (case_tac "Numeral0 < m")
+  apply (tactic {* zdiv_undefined_case_tac "m = 0" 1 *})
+  apply (case_tac "0 < m")
    apply (simp add: zcong_zmod_eq)
   apply (rule_tac t = m in zminus_zminus [THEN subst])
   apply (subst zcong_zminus)
   apply (subst zcong_zmod_eq)
    apply arith

 
 
 subsection {* Modulo *}
 
 lemma zmod_zdvd_zmod:
-    "Numeral0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
+    "0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
   apply (unfold dvd_def)
   apply auto
   apply (subst zcong_zmod_eq [symmetric])
    prefer 2
    apply (subst zcong_iff_lin)

 subsection {* Extended GCD *}
 
 declare xzgcda.simps [simp del]
 
 lemma aux1:
-  "zgcd (r', r) = k --> Numeral0 < r -->
+  "zgcd (r', r) = k --> 0 < r -->
     (\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn))"
   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 (case_tac "r' mod r = Numeral0")
+  apply (case_tac "r' mod r = 0")
    prefer 2
    apply (frule_tac a = "r'" in pos_mod_sign)
    apply auto
    apply arith
   apply (rule exI)

   apply auto
   apply (simp add: zabs_def)
   done
 
 lemma aux2:
-  "(\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn)) --> Numeral0 < r -->
+  "(\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn)) --> 0 < r -->
     zgcd (r', r) = k"
   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 simp add: linorder_not_le)
-  apply (case_tac "r' mod r = Numeral0")
+  apply (case_tac "r' mod r = 0")
    prefer 2
    apply (frule_tac a = "r'" in pos_mod_sign)
    apply auto
    apply arith
   apply (erule_tac P = "xzgcda ?u = ?v" in rev_mp)

   apply auto
   apply (simp add: zabs_def)
   done
 
 lemma xzgcd_correct:
-    "Numeral0 < n ==> (zgcd (m, n) = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
+    "0 < n ==> (zgcd (m, n) = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
   apply (unfold xzgcd_def)
   apply (rule iffI)
    apply (rule_tac [2] aux2 [THEN mp, THEN mp])
     apply (rule aux1 [THEN mp, THEN mp])
      apply auto

 
 lemma order_le_neq_implies_less: "(x::'a::order) \<le> y ==> x \<noteq> y ==> x < y"
   by (rule iffD2 [OF order_less_le conjI])
 
 lemma xzgcda_linear [rule_format]:
-  "Numeral0 < r --> xzgcda (m, n, r', r, s', s, t', t) = (rn, sn, tn) -->
+  "0 < r --> xzgcda (m, n, r', r, s', s, t', t) = (rn, sn, tn) -->
     r' = s' * m + t' * n -->  r = s * m + t * n --> rn = sn * m + tn * n"
   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 xzgcda.simps)
   apply (simp (no_asm))
   apply (rule impI)+
-  apply (case_tac "r' mod r = Numeral0")
+  apply (case_tac "r' mod r = 0")
    apply (simp add: xzgcda.simps)
    apply clarify
-  apply (subgoal_tac "Numeral0 < r' mod r")
+  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 aux)
       apply auto
   done
 
 lemma xzgcd_linear:
-    "Numeral0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
+    "0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
   apply (unfold xzgcd_def)
   apply (erule xzgcda_linear)
     apply assumption
    apply auto
   done
 
 lemma zgcd_ex_linear:
-    "Numeral0 < n ==> zgcd (m, n) = k ==> (\<exists>s t. k = s * m + t * n)"
+    "0 < n ==> zgcd (m, n) = k ==> (\<exists>s t. k = s * m + t * n)"
   apply (simp add: xzgcd_correct)
   apply safe
   apply (rule exI)+
   apply (erule xzgcd_linear)
   apply auto
   done
 
 lemma zcong_lineq_ex:
-    "Numeral0 < n ==> zgcd (a, n) = Numeral1 ==> \<exists>x. [a * x = Numeral1] (mod n)"
-  apply (cut_tac m = a and n = n and k = "Numeral1" in zgcd_ex_linear)
+    "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 (rule_tac x = s in exI)
   apply (rule_tac b = "s * a + t * n" in zcong_trans)
    prefer 2
    apply simp
   apply (unfold zcong_def)
   apply (simp (no_asm) add: zmult_commute zdvd_zminus_iff)
   done
 
 lemma zcong_lineq_unique:
-  "Numeral0 < n ==>
-    zgcd (a, n) = Numeral1 ==> \<exists>!x. Numeral0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
+  "0 < n ==>
+    zgcd (a, n) = 1 ==> \<exists>!x. 0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
   apply auto
    apply (rule_tac [2] zcong_zless_imp_eq)
        apply (tactic {* stac (thm "zcong_cancel2" RS sym) 6 *})
          apply (rule_tac [8] zcong_trans)
           apply (simp_all (no_asm_simp))

   apply safe
     apply (simp_all (no_asm_simp) add: pos_mod_bound pos_mod_sign)
   apply (subst zcong_zmod)
   apply (subst zmod_zmult1_eq [symmetric])
   apply (subst zcong_zmod [symmetric])
-  apply (subgoal_tac "[a * x * b = Numeral1 * b] (mod n)")
+  apply (subgoal_tac "[a * x * b = 1 * b] (mod n)")
    apply (rule_tac [2] zcong_zmult)
     apply (simp_all add: zmult_assoc)
   done
 
 end