--- 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])