src/HOL/NumberTheory/IntPrimes.thy
changeset 11049 7eef34adb852
parent 10147 178deaacb244
child 11701 3d51fbf81c17
     1.1 --- a/src/HOL/NumberTheory/IntPrimes.thy	Sat Feb 03 17:43:34 2001 +0100
     1.2 +++ b/src/HOL/NumberTheory/IntPrimes.thy	Sun Feb 04 19:31:13 2001 +0100
     1.3 @@ -1,34 +1,841 @@
     1.4 -(*  Title:	IntPrimes.thy
     1.5 +(*  Title:      HOL/NumberTheory/IntPrimes.thy
     1.6      ID:         $Id$
     1.7 -    Author:	Thomas M. Rasmussen
     1.8 -    Copyright	2000  University of Cambridge
     1.9 +    Author:     Thomas M. Rasmussen
    1.10 +    Copyright   2000  University of Cambridge
    1.11  *)
    1.12  
    1.13 -IntPrimes = Primes +
    1.14 +header {* Divisibility and prime numbers (on integers) *}
    1.15 +
    1.16 +theory IntPrimes = Primes:
    1.17 +
    1.18 +text {*
    1.19 +  The @{text dvd} relation, GCD, Euclid's extended algorithm, primes,
    1.20 +  congruences (all on the Integers).  Comparable to theory @{text
    1.21 +  Primes}, but @{text dvd} is included here as it is not present in
    1.22 +  main HOL.  Also includes extended GCD and congruences not present in
    1.23 +  @{text Primes}.
    1.24 +*}
    1.25 +
    1.26 +
    1.27 +subsection {* Definitions *}
    1.28  
    1.29  consts
    1.30 -  xzgcda   :: "int*int*int*int*int*int*int*int => int*int*int"
    1.31 -  xzgcd    :: "[int,int] => int*int*int" 
    1.32 -  zprime   :: int set
    1.33 -  zcong    :: [int,int,int] => bool     ("(1[_ = _] '(mod _'))")
    1.34 -  
    1.35 -recdef xzgcda 
    1.36 -       "measure ((%(m,n,r',r,s',s,t',t).(nat r))
    1.37 -                 ::int*int*int*int*int*int*int*int=>nat)"
    1.38 -        simpset "simpset() addsimps [pos_mod_bound]"
    1.39 -       "xzgcda (m,n,r',r,s',s,t',t) = 
    1.40 -          (if r<=#0 then (r',s',t') else  
    1.41 -           xzgcda(m,n,r,r' mod r,s,s'-(r' div r)*s,t,t'-(r' div r)*t))"
    1.42 +  xzgcda :: "int * int * int * int * int * int * int * int => int * int * int"
    1.43 +  xzgcd :: "int => int => int * int * int"
    1.44 +  zprime :: "int set"
    1.45 +  zcong :: "int => int => int => bool"    ("(1[_ = _] '(mod _'))")
    1.46 +
    1.47 +recdef xzgcda
    1.48 +  "measure ((\<lambda>(m, n, r', r, s', s, t', t). nat r)
    1.49 +    :: int * int * int * int *int * int * int * int => nat)"
    1.50 +  "xzgcda (m, n, r', r, s', s, t', t) =
    1.51 +    (if r \<le> #0 then (r', s', t')
    1.52 +     else xzgcda (m, n, r, r' mod r, s, s' - (r' div r) * s, t, t' - (r' div r) * t))"
    1.53 +  (hints simp: pos_mod_bound)
    1.54  
    1.55  constdefs
    1.56 -  zgcd     :: "int*int => int"              
    1.57 -      "zgcd == %(x,y). int (gcd(nat (abs x), nat (abs y)))"
    1.58 +  zgcd :: "int * int => int"
    1.59 +  "zgcd == \<lambda>(x,y). int (gcd (nat (abs x), nat (abs y)))"
    1.60  
    1.61  defs
    1.62 -  xzgcd_def    "xzgcd m n == xzgcda (m,n,m,n,#1,#0,#0,#1)"
    1.63 +  xzgcd_def: "xzgcd m n == xzgcda (m, n, m, n, #1, #0, #0, #1)"
    1.64 +  zprime_def: "zprime == {p. #1 < p \<and> (\<forall>m. m dvd p --> m = #1 \<or> m = p)}"
    1.65 +  zcong_def: "[a = b] (mod m) == m dvd (a - b)"
    1.66 +
    1.67 +
    1.68 +lemma zabs_eq_iff:
    1.69 +    "(abs (z::int) = w) = (z = w \<and> #0 <= z \<or> z = -w \<and> z < #0)"
    1.70 +  apply (auto simp add: zabs_def)
    1.71 +  done
    1.72 +
    1.73 +
    1.74 +text {* \medskip @{term gcd} lemmas *}
    1.75 +
    1.76 +lemma gcd_add1_eq: "gcd (m + k, k) = gcd (m + k, m)"
    1.77 +  apply (simp add: gcd_commute)
    1.78 +  done
    1.79 +
    1.80 +lemma gcd_diff2: "m \<le> n ==> gcd (n, n - m) = gcd (n, m)"
    1.81 +  apply (subgoal_tac "n = m + (n - m)")
    1.82 +   apply (erule ssubst, rule gcd_add1_eq)
    1.83 +  apply simp
    1.84 +  done
    1.85 +
    1.86 +
    1.87 +subsection {* Divides relation *}
    1.88 +
    1.89 +lemma zdvd_0_right [iff]: "(m::int) dvd #0"
    1.90 +  apply (unfold dvd_def)
    1.91 +  apply (blast intro: zmult_0_right [symmetric])
    1.92 +  done
    1.93 +
    1.94 +lemma zdvd_0_left [iff]: "(#0 dvd (m::int)) = (m = #0)"
    1.95 +  apply (unfold dvd_def)
    1.96 +  apply auto
    1.97 +  done
    1.98 +
    1.99 +lemma zdvd_1_left [iff]: "#1 dvd (m::int)"
   1.100 +  apply (unfold dvd_def)
   1.101 +  apply simp
   1.102 +  done
   1.103 +
   1.104 +lemma zdvd_refl [simp]: "m dvd (m::int)"
   1.105 +  apply (unfold dvd_def)
   1.106 +  apply (blast intro: zmult_1_right [symmetric])
   1.107 +  done
   1.108 +
   1.109 +lemma zdvd_trans: "m dvd n ==> n dvd k ==> m dvd (k::int)"
   1.110 +  apply (unfold dvd_def)
   1.111 +  apply (blast intro: zmult_assoc)
   1.112 +  done
   1.113 +
   1.114 +lemma zdvd_zminus_iff: "(m dvd -n) = (m dvd (n::int))"
   1.115 +  apply (unfold dvd_def)
   1.116 +  apply auto
   1.117 +   apply (rule_tac [!] x = "-k" in exI)
   1.118 +  apply auto
   1.119 +  done
   1.120 +
   1.121 +lemma zdvd_zminus2_iff: "(-m dvd n) = (m dvd (n::int))"
   1.122 +  apply (unfold dvd_def)
   1.123 +  apply auto
   1.124 +   apply (rule_tac [!] x = "-k" in exI)
   1.125 +  apply auto
   1.126 +  done
   1.127 +
   1.128 +lemma zdvd_anti_sym:
   1.129 +    "#0 < m ==> #0 < n ==> m dvd n ==> n dvd m ==> m = (n::int)"
   1.130 +  apply (unfold dvd_def)
   1.131 +  apply auto
   1.132 +  apply (simp add: zmult_assoc zmult_eq_self_iff int_0_less_mult_iff zmult_eq_1_iff)
   1.133 +  done
   1.134 +
   1.135 +lemma zdvd_zadd: "k dvd m ==> k dvd n ==> k dvd (m + n :: int)"
   1.136 +  apply (unfold dvd_def)
   1.137 +  apply (blast intro: zadd_zmult_distrib2 [symmetric])
   1.138 +  done
   1.139 +
   1.140 +lemma zdvd_zdiff: "k dvd m ==> k dvd n ==> k dvd (m - n :: int)"
   1.141 +  apply (unfold dvd_def)
   1.142 +  apply (blast intro: zdiff_zmult_distrib2 [symmetric])
   1.143 +  done
   1.144 +
   1.145 +lemma zdvd_zdiffD: "k dvd m - n ==> k dvd n ==> k dvd (m::int)"
   1.146 +  apply (subgoal_tac "m = n + (m - n)")
   1.147 +   apply (erule ssubst)
   1.148 +   apply (blast intro: zdvd_zadd)
   1.149 +  apply simp
   1.150 +  done
   1.151 +
   1.152 +lemma zdvd_zmult: "k dvd (n::int) ==> k dvd m * n"
   1.153 +  apply (unfold dvd_def)
   1.154 +  apply (blast intro: zmult_left_commute)
   1.155 +  done
   1.156 +
   1.157 +lemma zdvd_zmult2: "k dvd (m::int) ==> k dvd m * n"
   1.158 +  apply (subst zmult_commute)
   1.159 +  apply (erule zdvd_zmult)
   1.160 +  done
   1.161 +
   1.162 +lemma [iff]: "(k::int) dvd m * k"
   1.163 +  apply (rule zdvd_zmult)
   1.164 +  apply (rule zdvd_refl)
   1.165 +  done
   1.166 +
   1.167 +lemma [iff]: "(k::int) dvd k * m"
   1.168 +  apply (rule zdvd_zmult2)
   1.169 +  apply (rule zdvd_refl)
   1.170 +  done
   1.171 +
   1.172 +lemma zdvd_zmultD2: "j * k dvd n ==> j dvd (n::int)"
   1.173 +  apply (unfold dvd_def)
   1.174 +  apply (simp add: zmult_assoc)
   1.175 +  apply blast
   1.176 +  done
   1.177 +
   1.178 +lemma zdvd_zmultD: "j * k dvd n ==> k dvd (n::int)"
   1.179 +  apply (rule zdvd_zmultD2)
   1.180 +  apply (subst zmult_commute)
   1.181 +  apply assumption
   1.182 +  done
   1.183 +
   1.184 +lemma zdvd_zmult_mono: "i dvd m ==> j dvd (n::int) ==> i * j dvd m * n"
   1.185 +  apply (unfold dvd_def)
   1.186 +  apply clarify
   1.187 +  apply (rule_tac x = "k * ka" in exI)
   1.188 +  apply (simp add: zmult_ac)
   1.189 +  done
   1.190 +
   1.191 +lemma zdvd_reduce: "(k dvd n + k * m) = (k dvd (n::int))"
   1.192 +  apply (rule iffI)
   1.193 +   apply (erule_tac [2] zdvd_zadd)
   1.194 +   apply (subgoal_tac "n = (n + k * m) - k * m")
   1.195 +    apply (erule ssubst)
   1.196 +    apply (erule zdvd_zdiff)
   1.197 +    apply simp_all
   1.198 +  done
   1.199 +
   1.200 +lemma zdvd_zmod: "f dvd m ==> f dvd (n::int) ==> f dvd m mod n"
   1.201 +  apply (unfold dvd_def)
   1.202 +  apply (auto simp add: zmod_zmult_zmult1)
   1.203 +  done
   1.204 +
   1.205 +lemma zdvd_zmod_imp_zdvd: "k dvd m mod n ==> k dvd n ==> k dvd (m::int)"
   1.206 +  apply (subgoal_tac "k dvd n * (m div n) + m mod n")
   1.207 +   apply (simp add: zmod_zdiv_equality [symmetric])
   1.208 +  apply (simp add: zdvd_zadd zdvd_zmult2)
   1.209 +  done
   1.210 +
   1.211 +lemma zdvd_iff_zmod_eq_0: "(k dvd n) = (n mod (k::int) = #0)"
   1.212 +  apply (unfold dvd_def)
   1.213 +  apply auto
   1.214 +  done
   1.215 +
   1.216 +lemma zdvd_not_zless: "#0 < m ==> m < n ==> \<not> n dvd (m::int)"
   1.217 +  apply (unfold dvd_def)
   1.218 +  apply auto
   1.219 +  apply (subgoal_tac "#0 < n")
   1.220 +   prefer 2
   1.221 +   apply (blast intro: zless_trans)
   1.222 +  apply (simp add: int_0_less_mult_iff)
   1.223 +  apply (subgoal_tac "n * k < n * #1")
   1.224 +   apply (drule zmult_zless_cancel1 [THEN iffD1])
   1.225 +   apply auto
   1.226 +  done
   1.227 +
   1.228 +lemma int_dvd_iff: "(int m dvd z) = (m dvd nat (abs z))"
   1.229 +  apply (auto simp add: dvd_def nat_abs_mult_distrib)
   1.230 +  apply (auto simp add: nat_eq_iff zabs_eq_iff)
   1.231 +   apply (rule_tac [2] x = "-(int k)" in exI)
   1.232 +  apply (auto simp add: zmult_int [symmetric])
   1.233 +  done
   1.234 +
   1.235 +lemma dvd_int_iff: "(z dvd int m) = (nat (abs z) dvd m)"
   1.236 +  apply (auto simp add: dvd_def zabs_def zmult_int [symmetric])
   1.237 +    apply (rule_tac [3] x = "nat k" in exI)
   1.238 +    apply (rule_tac [2] x = "-(int k)" in exI)
   1.239 +    apply (rule_tac x = "nat (-k)" in exI)
   1.240 +    apply (cut_tac [3] k = m in int_less_0_conv)
   1.241 +    apply (cut_tac k = m in int_less_0_conv)
   1.242 +    apply (auto simp add: int_0_le_mult_iff zmult_less_0_iff
   1.243 +      nat_mult_distrib [symmetric] nat_eq_iff2)
   1.244 +  done
   1.245 +
   1.246 +lemma nat_dvd_iff: "(nat z dvd m) = (if #0 \<le> z then (z dvd int m) else m = 0)"
   1.247 +  apply (auto simp add: dvd_def zmult_int [symmetric])
   1.248 +  apply (rule_tac x = "nat k" in exI)
   1.249 +  apply (cut_tac k = m in int_less_0_conv)
   1.250 +  apply (auto simp add: int_0_le_mult_iff zmult_less_0_iff
   1.251 +    nat_mult_distrib [symmetric] nat_eq_iff2)
   1.252 +  done
   1.253 +
   1.254 +lemma zminus_dvd_iff [iff]: "(-z dvd w) = (z dvd (w::int))"
   1.255 +  apply (auto simp add: dvd_def)
   1.256 +   apply (rule_tac [!] x = "-k" in exI)
   1.257 +   apply auto
   1.258 +  done
   1.259 +
   1.260 +lemma dvd_zminus_iff [iff]: "(z dvd -w) = (z dvd (w::int))"
   1.261 +  apply (auto simp add: dvd_def)
   1.262 +   apply (drule zminus_equation [THEN iffD1])
   1.263 +   apply (rule_tac [!] x = "-k" in exI)
   1.264 +   apply auto
   1.265 +  done
   1.266 +
   1.267 +
   1.268 +subsection {* Euclid's Algorithm and GCD *}
   1.269 +
   1.270 +lemma zgcd_0 [simp]: "zgcd (m, #0) = abs m"
   1.271 +  apply (simp add: zgcd_def zabs_def)
   1.272 +  done
   1.273 +
   1.274 +lemma zgcd_0_left [simp]: "zgcd (#0, m) = abs m"
   1.275 +  apply (simp add: zgcd_def zabs_def)
   1.276 +  done
   1.277 +
   1.278 +lemma zgcd_zminus [simp]: "zgcd (-m, n) = zgcd (m, n)"
   1.279 +  apply (simp add: zgcd_def)
   1.280 +  done
   1.281 +
   1.282 +lemma zgcd_zminus2 [simp]: "zgcd (m, -n) = zgcd (m, n)"
   1.283 +  apply (simp add: zgcd_def)
   1.284 +  done
   1.285 +
   1.286 +lemma zgcd_non_0: "#0 < n ==> zgcd (m, n) = zgcd (n, m mod n)"
   1.287 +  apply (frule_tac b = n and a = m in pos_mod_sign)
   1.288 +  apply (simp add: zgcd_def zabs_def nat_mod_distrib)
   1.289 +  apply (cut_tac a = "-m" and b = n in zmod_zminus1_eq_if)
   1.290 +  apply (auto simp add: gcd_non_0 nat_mod_distrib [symmetric] zmod_zminus1_eq_if)
   1.291 +  apply (frule_tac a = m in pos_mod_bound)
   1.292 +  apply (simp add: nat_diff_distrib)
   1.293 +  apply (rule gcd_diff2)
   1.294 +  apply (simp add: nat_le_eq_zle)
   1.295 +  done
   1.296 +
   1.297 +lemma zgcd_eq: "zgcd (m, n) = zgcd (n, m mod n)"
   1.298 +  apply (tactic {* zdiv_undefined_case_tac "n = #0" 1 *})
   1.299 +  apply (auto simp add: linorder_neq_iff zgcd_non_0)
   1.300 +  apply (cut_tac m = "-m" and n = "-n" in zgcd_non_0)
   1.301 +   apply auto
   1.302 +  done
   1.303 +
   1.304 +lemma zgcd_1 [simp]: "zgcd (m, #1) = #1"
   1.305 +  apply (simp add: zgcd_def zabs_def)
   1.306 +  done
   1.307 +
   1.308 +lemma zgcd_0_1_iff [simp]: "(zgcd (#0, m) = #1) = (abs m = #1)"
   1.309 +  apply (simp add: zgcd_def zabs_def)
   1.310 +  done
   1.311 +
   1.312 +lemma zgcd_zdvd1 [iff]: "zgcd (m, n) dvd m"
   1.313 +  apply (simp add: zgcd_def zabs_def int_dvd_iff)
   1.314 +  done
   1.315 +
   1.316 +lemma zgcd_zdvd2 [iff]: "zgcd (m, n) dvd n"
   1.317 +  apply (simp add: zgcd_def zabs_def int_dvd_iff)
   1.318 +  done
   1.319 +
   1.320 +lemma zgcd_greatest_iff: "k dvd zgcd (m, n) = (k dvd m \<and> k dvd n)"
   1.321 +  apply (simp add: zgcd_def zabs_def int_dvd_iff dvd_int_iff nat_dvd_iff)
   1.322 +  done
   1.323 +
   1.324 +lemma zgcd_commute: "zgcd (m, n) = zgcd (n, m)"
   1.325 +  apply (simp add: zgcd_def gcd_commute)
   1.326 +  done
   1.327 +
   1.328 +lemma zgcd_1_left [simp]: "zgcd (#1, m) = #1"
   1.329 +  apply (simp add: zgcd_def gcd_1_left)
   1.330 +  done
   1.331 +
   1.332 +lemma zgcd_assoc: "zgcd (zgcd (k, m), n) = zgcd (k, zgcd (m, n))"
   1.333 +  apply (simp add: zgcd_def gcd_assoc)
   1.334 +  done
   1.335 +
   1.336 +lemma zgcd_left_commute: "zgcd (k, zgcd (m, n)) = zgcd (m, zgcd (k, n))"
   1.337 +  apply (rule zgcd_commute [THEN trans])
   1.338 +  apply (rule zgcd_assoc [THEN trans])
   1.339 +  apply (rule zgcd_commute [THEN arg_cong])
   1.340 +  done
   1.341 +
   1.342 +lemmas zgcd_ac = zgcd_assoc zgcd_commute zgcd_left_commute
   1.343 +  -- {* addition is an AC-operator *}
   1.344 +
   1.345 +lemma zgcd_zmult_distrib2: "#0 \<le> k ==> k * zgcd (m, n) = zgcd (k * m, k * n)"
   1.346 +  apply (simp del: zmult_zminus_right
   1.347 +    add: zmult_zminus_right [symmetric] nat_mult_distrib zgcd_def zabs_def
   1.348 +    zmult_less_0_iff gcd_mult_distrib2 [symmetric] zmult_int [symmetric])
   1.349 +  done
   1.350 +
   1.351 +lemma zgcd_zmult_distrib2_abs: "zgcd (k * m, k * n) = abs k * zgcd (m, n)"
   1.352 +  apply (simp add: zabs_def zgcd_zmult_distrib2)
   1.353 +  done
   1.354 +
   1.355 +lemma zgcd_self [simp]: "#0 \<le> m ==> zgcd (m, m) = m"
   1.356 +  apply (cut_tac k = m and m = "#1" and n = "#1" in zgcd_zmult_distrib2)
   1.357 +   apply simp_all
   1.358 +  done
   1.359 +
   1.360 +lemma zgcd_zmult_eq_self [simp]: "#0 \<le> k ==> zgcd (k, k * n) = k"
   1.361 +  apply (cut_tac k = k and m = "#1" and n = n in zgcd_zmult_distrib2)
   1.362 +   apply simp_all
   1.363 +  done
   1.364 +
   1.365 +lemma zgcd_zmult_eq_self2 [simp]: "#0 \<le> k ==> zgcd (k * n, k) = k"
   1.366 +  apply (cut_tac k = k and m = n and n = "#1" in zgcd_zmult_distrib2)
   1.367 +   apply simp_all
   1.368 +  done
   1.369 +
   1.370 +lemma aux: "zgcd (n, k) = #1 ==> k dvd m * n ==> #0 \<le> m ==> k dvd m"
   1.371 +  apply (subgoal_tac "m = zgcd (m * n, m * k)")
   1.372 +   apply (erule ssubst, rule zgcd_greatest_iff [THEN iffD2])
   1.373 +   apply (simp_all add: zgcd_zmult_distrib2 [symmetric] int_0_le_mult_iff)
   1.374 +  done
   1.375 +
   1.376 +lemma zrelprime_zdvd_zmult: "zgcd (n, k) = #1 ==> k dvd m * n ==> k dvd m"
   1.377 +  apply (case_tac "#0 \<le> m")
   1.378 +   apply (blast intro: aux)
   1.379 +  apply (subgoal_tac "k dvd -m")
   1.380 +   apply (rule_tac [2] aux)
   1.381 +     apply auto
   1.382 +  done
   1.383 +
   1.384 +lemma zprime_imp_zrelprime:
   1.385 +    "p \<in> zprime ==> \<not> p dvd n ==> zgcd (n, p) = #1"
   1.386 +  apply (unfold zprime_def)
   1.387 +  apply auto
   1.388 +  done
   1.389 +
   1.390 +lemma zless_zprime_imp_zrelprime:
   1.391 +    "p \<in> zprime ==> #0 < n ==> n < p ==> zgcd (n, p) = #1"
   1.392 +  apply (erule zprime_imp_zrelprime)
   1.393 +  apply (erule zdvd_not_zless)
   1.394 +  apply assumption
   1.395 +  done
   1.396 +
   1.397 +lemma zprime_zdvd_zmult:
   1.398 +    "#0 \<le> (m::int) ==> p \<in> zprime ==> p dvd m * n ==> p dvd m \<or> p dvd n"
   1.399 +  apply safe
   1.400 +  apply (rule zrelprime_zdvd_zmult)
   1.401 +   apply (rule zprime_imp_zrelprime)
   1.402 +    apply auto
   1.403 +  done
   1.404 +
   1.405 +lemma zgcd_zadd_zmult [simp]: "zgcd (m + n * k, n) = zgcd (m, n)"
   1.406 +  apply (rule zgcd_eq [THEN trans])
   1.407 +  apply (simp add: zmod_zadd1_eq)
   1.408 +  apply (rule zgcd_eq [symmetric])
   1.409 +  done
   1.410 +
   1.411 +lemma zgcd_zdvd_zgcd_zmult: "zgcd (m, n) dvd zgcd (k * m, n)"
   1.412 +  apply (simp add: zgcd_greatest_iff)
   1.413 +  apply (blast intro: zdvd_trans)
   1.414 +  done
   1.415 +
   1.416 +lemma zgcd_zmult_zdvd_zgcd:
   1.417 +    "zgcd (k, n) = #1 ==> zgcd (k * m, n) dvd zgcd (m, n)"
   1.418 +  apply (simp add: zgcd_greatest_iff)
   1.419 +  apply (rule_tac n = k in zrelprime_zdvd_zmult)
   1.420 +   prefer 2
   1.421 +   apply (simp add: zmult_commute)
   1.422 +  apply (subgoal_tac "zgcd (k, zgcd (k * m, n)) = zgcd (k * m, zgcd (k, n))")
   1.423 +   apply simp
   1.424 +  apply (simp (no_asm) add: zgcd_ac)
   1.425 +  done
   1.426 +
   1.427 +lemma zgcd_zmult_cancel: "zgcd (k, n) = #1 ==> zgcd (k * m, n) = zgcd (m, n)"
   1.428 +  apply (simp add: zgcd_def nat_abs_mult_distrib gcd_mult_cancel)
   1.429 +  done
   1.430 +
   1.431 +lemma zgcd_zgcd_zmult:
   1.432 +    "zgcd (k, m) = #1 ==> zgcd (n, m) = #1 ==> zgcd (k * n, m) = #1"
   1.433 +  apply (simp (no_asm_simp) add: zgcd_zmult_cancel)
   1.434 +  done
   1.435 +
   1.436 +lemma zdvd_iff_zgcd: "#0 < m ==> (m dvd n) = (zgcd (n, m) = m)"
   1.437 +  apply safe
   1.438 +   apply (rule_tac [2] n = "zgcd (n, m)" in zdvd_trans)
   1.439 +    apply (rule_tac [3] zgcd_zdvd1)
   1.440 +   apply simp_all
   1.441 +  apply (unfold dvd_def)
   1.442 +  apply auto
   1.443 +  done
   1.444 +
   1.445 +
   1.446 +subsection {* Congruences *}
   1.447 +
   1.448 +lemma zcong_1 [simp]: "[a = b] (mod #1)"
   1.449 +  apply (unfold zcong_def)
   1.450 +  apply auto
   1.451 +  done
   1.452 +
   1.453 +lemma zcong_refl [simp]: "[k = k] (mod m)"
   1.454 +  apply (unfold zcong_def)
   1.455 +  apply auto
   1.456 +  done
   1.457  
   1.458 -  zprime_def   "zprime == {p. #1<p & (ALL m. m dvd p --> m=#1 | m=p)}"
   1.459 +lemma zcong_sym: "[a = b] (mod m) = [b = a] (mod m)"
   1.460 +  apply (unfold zcong_def dvd_def)
   1.461 +  apply auto
   1.462 +   apply (rule_tac [!] x = "-k" in exI)
   1.463 +   apply auto
   1.464 +  done
   1.465 +
   1.466 +lemma zcong_zadd:
   1.467 +    "[a = b] (mod m) ==> [c = d] (mod m) ==> [a + c = b + d] (mod m)"
   1.468 +  apply (unfold zcong_def)
   1.469 +  apply (rule_tac s = "(a - b) + (c - d)" in subst)
   1.470 +   apply (rule_tac [2] zdvd_zadd)
   1.471 +    apply auto
   1.472 +  done
   1.473 +
   1.474 +lemma zcong_zdiff:
   1.475 +    "[a = b] (mod m) ==> [c = d] (mod m) ==> [a - c = b - d] (mod m)"
   1.476 +  apply (unfold zcong_def)
   1.477 +  apply (rule_tac s = "(a - b) - (c - d)" in subst)
   1.478 +   apply (rule_tac [2] zdvd_zdiff)
   1.479 +    apply auto
   1.480 +  done
   1.481 +
   1.482 +lemma zcong_trans:
   1.483 +    "[a = b] (mod m) ==> [b = c] (mod m) ==> [a = c] (mod m)"
   1.484 +  apply (unfold zcong_def dvd_def)
   1.485 +  apply auto
   1.486 +  apply (rule_tac x = "k + ka" in exI)
   1.487 +  apply (simp add: zadd_ac zadd_zmult_distrib2)
   1.488 +  done
   1.489 +
   1.490 +lemma zcong_zmult:
   1.491 +    "[a = b] (mod m) ==> [c = d] (mod m) ==> [a * c = b * d] (mod m)"
   1.492 +  apply (rule_tac b = "b * c" in zcong_trans)
   1.493 +   apply (unfold zcong_def)
   1.494 +   apply (rule_tac s = "c * (a - b)" in subst)
   1.495 +    apply (rule_tac [3] s = "b * (c - d)" in subst)
   1.496 +     prefer 4
   1.497 +     apply (blast intro: zdvd_zmult)
   1.498 +    prefer 2
   1.499 +    apply (blast intro: zdvd_zmult)
   1.500 +   apply (simp_all add: zdiff_zmult_distrib2 zmult_commute)
   1.501 +  done
   1.502 +
   1.503 +lemma zcong_scalar: "[a = b] (mod m) ==> [a * k = b * k] (mod m)"
   1.504 +  apply (rule zcong_zmult)
   1.505 +  apply simp_all
   1.506 +  done
   1.507 +
   1.508 +lemma zcong_scalar2: "[a = b] (mod m) ==> [k * a = k * b] (mod m)"
   1.509 +  apply (rule zcong_zmult)
   1.510 +  apply simp_all
   1.511 +  done
   1.512 +
   1.513 +lemma zcong_zmult_self: "[a * m = b * m] (mod m)"
   1.514 +  apply (unfold zcong_def)
   1.515 +  apply (rule zdvd_zdiff)
   1.516 +   apply simp_all
   1.517 +  done
   1.518 +
   1.519 +lemma zcong_square:
   1.520 +  "p \<in> zprime ==> #0 < a ==> [a * a = #1] (mod p)
   1.521 +    ==> [a = #1] (mod p) \<or> [a = p - #1] (mod p)"
   1.522 +  apply (unfold zcong_def)
   1.523 +  apply (rule zprime_zdvd_zmult)
   1.524 +    apply (rule_tac [3] s = "a * a - #1 + p * (#1 - a)" in subst)
   1.525 +     prefer 4
   1.526 +     apply (simp add: zdvd_reduce)
   1.527 +    apply (simp_all add: zdiff_zmult_distrib zmult_commute zdiff_zmult_distrib2)
   1.528 +  done
   1.529 +
   1.530 +lemma zcong_cancel:
   1.531 +  "#0 \<le> m ==>
   1.532 +    zgcd (k, m) = #1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
   1.533 +  apply safe
   1.534 +   prefer 2
   1.535 +   apply (blast intro: zcong_scalar)
   1.536 +  apply (case_tac "b < a")
   1.537 +   prefer 2
   1.538 +   apply (subst zcong_sym)
   1.539 +   apply (unfold zcong_def)
   1.540 +   apply (rule_tac [!] zrelprime_zdvd_zmult)
   1.541 +     apply (simp_all add: zdiff_zmult_distrib)
   1.542 +  apply (subgoal_tac "m dvd (-(a * k - b * k))")
   1.543 +   apply (simp add: zminus_zdiff_eq)
   1.544 +  apply (subst zdvd_zminus_iff)
   1.545 +  apply assumption
   1.546 +  done
   1.547 +
   1.548 +lemma zcong_cancel2:
   1.549 +  "#0 \<le> m ==>
   1.550 +    zgcd (k, m) = #1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
   1.551 +  apply (simp add: zmult_commute zcong_cancel)
   1.552 +  done
   1.553 +
   1.554 +lemma zcong_zgcd_zmult_zmod:
   1.555 +  "[a = b] (mod m) ==> [a = b] (mod n) ==> zgcd (m, n) = #1
   1.556 +    ==> [a = b] (mod m * n)"
   1.557 +  apply (unfold zcong_def dvd_def)
   1.558 +  apply auto
   1.559 +  apply (subgoal_tac "m dvd n * ka")
   1.560 +   apply (subgoal_tac "m dvd ka")
   1.561 +    apply (case_tac [2] "#0 \<le> ka")
   1.562 +     prefer 3
   1.563 +     apply (subst zdvd_zminus_iff [symmetric])
   1.564 +     apply (rule_tac n = n in zrelprime_zdvd_zmult)
   1.565 +      apply (simp add: zgcd_commute)
   1.566 +     apply (simp add: zmult_commute zdvd_zminus_iff)
   1.567 +    prefer 2
   1.568 +    apply (rule_tac n = n in zrelprime_zdvd_zmult)
   1.569 +     apply (simp add: zgcd_commute)
   1.570 +    apply (simp add: zmult_commute)
   1.571 +   apply (auto simp add: dvd_def)
   1.572 +  apply (blast intro: sym)
   1.573 +  done
   1.574 +
   1.575 +lemma zcong_zless_imp_eq:
   1.576 +  "#0 \<le> a ==>
   1.577 +    a < m ==> #0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
   1.578 +  apply (unfold zcong_def dvd_def)
   1.579 +  apply auto
   1.580 +  apply (drule_tac f = "\<lambda>z. z mod m" in arg_cong)
   1.581 +  apply (cut_tac z = a and w = b in zless_linear)
   1.582 +  apply auto
   1.583 +   apply (subgoal_tac [2] "(a - b) mod m = a - b")
   1.584 +    apply (rule_tac [3] mod_pos_pos_trivial)
   1.585 +     apply auto
   1.586 +  apply (subgoal_tac "(m + (a - b)) mod m = m + (a - b)")
   1.587 +   apply (rule_tac [2] mod_pos_pos_trivial)
   1.588 +    apply auto
   1.589 +  done
   1.590 +
   1.591 +lemma zcong_square_zless:
   1.592 +  "p \<in> zprime ==> #0 < a ==> a < p ==>
   1.593 +    [a * a = #1] (mod p) ==> a = #1 \<or> a = p - #1"
   1.594 +  apply (cut_tac p = p and a = a in zcong_square)
   1.595 +     apply (simp add: zprime_def)
   1.596 +    apply (auto intro: zcong_zless_imp_eq)
   1.597 +  done
   1.598 +
   1.599 +lemma zcong_not:
   1.600 +    "#0 < a ==> a < m ==> #0 < b ==> b < a ==> \<not> [a = b] (mod m)"
   1.601 +  apply (unfold zcong_def)
   1.602 +  apply (rule zdvd_not_zless)
   1.603 +   apply auto
   1.604 +  done
   1.605 +
   1.606 +lemma zcong_zless_0:
   1.607 +    "#0 \<le> a ==> a < m ==> [a = #0] (mod m) ==> a = #0"
   1.608 +  apply (unfold zcong_def dvd_def)
   1.609 +  apply auto
   1.610 +  apply (subgoal_tac "#0 < m")
   1.611 +   apply (rotate_tac -1)
   1.612 +   apply (simp add: int_0_le_mult_iff)
   1.613 +   apply (subgoal_tac "m * k < m * #1")
   1.614 +    apply (drule zmult_zless_cancel1 [THEN iffD1])
   1.615 +    apply (auto simp add: linorder_neq_iff)
   1.616 +  done
   1.617 +
   1.618 +lemma zcong_zless_unique:
   1.619 +    "#0 < m ==> (\<exists>!b. #0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
   1.620 +  apply auto
   1.621 +   apply (subgoal_tac [2] "[b = y] (mod m)")
   1.622 +    apply (case_tac [2] "b = #0")
   1.623 +     apply (case_tac [3] "y = #0")
   1.624 +      apply (auto intro: zcong_trans zcong_zless_0 zcong_zless_imp_eq order_less_le
   1.625 +        simp add: zcong_sym)
   1.626 +  apply (unfold zcong_def dvd_def)
   1.627 +  apply (rule_tac x = "a mod m" in exI)
   1.628 +  apply (auto simp add: pos_mod_sign pos_mod_bound)
   1.629 +  apply (rule_tac x = "-(a div m)" in exI)
   1.630 +  apply (cut_tac a = a and b = m in zmod_zdiv_equality)
   1.631 +  apply auto
   1.632 +  done
   1.633 +
   1.634 +lemma zcong_iff_lin: "([a = b] (mod m)) = (\<exists>k. b = a + m * k)"
   1.635 +  apply (unfold zcong_def dvd_def)
   1.636 +  apply auto
   1.637 +   apply (rule_tac [!] x = "-k" in exI)
   1.638 +   apply auto
   1.639 +  done
   1.640 +
   1.641 +lemma zgcd_zcong_zgcd:
   1.642 +  "#0 < m ==>
   1.643 +    zgcd (a, m) = #1 ==> [a = b] (mod m) ==> zgcd (b, m) = #1"
   1.644 +  apply (auto simp add: zcong_iff_lin)
   1.645 +  done
   1.646 +
   1.647 +lemma aux: "a = c ==> b = d ==> a - b = c - (d::int)"
   1.648 +  apply auto
   1.649 +  done
   1.650 +
   1.651 +lemma aux: "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
   1.652 +  apply (rule_tac "s" = "(m * (a div m) + a mod m) - (m * (b div m) + b mod m)"
   1.653 +    in trans)
   1.654 +   prefer 2
   1.655 +   apply (simp add: zdiff_zmult_distrib2)
   1.656 +  apply (rule aux)
   1.657 +   apply (rule_tac [!] zmod_zdiv_equality)
   1.658 +  done
   1.659  
   1.660 -  zcong_def    "[a=b] (mod m) == m dvd (a-b)"
   1.661 +lemma zcong_zmod: "[a = b] (mod m) = [a mod m = b mod m] (mod m)"
   1.662 +  apply (unfold zcong_def)
   1.663 +  apply (rule_tac t = "a - b" in ssubst)
   1.664 +  apply (rule_tac "m" = "m" in aux)
   1.665 +  apply (rule trans)
   1.666 +   apply (rule_tac [2] k = m and m = "a div m - b div m" in zdvd_reduce)
   1.667 +  apply (simp add: zadd_commute)
   1.668 +  done
   1.669 +
   1.670 +lemma zcong_zmod_eq: "#0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
   1.671 +  apply auto
   1.672 +   apply (rule_tac m = m in zcong_zless_imp_eq)
   1.673 +       prefer 5
   1.674 +       apply (subst zcong_zmod [symmetric])
   1.675 +       apply (simp_all add: pos_mod_bound pos_mod_sign)
   1.676 +  apply (unfold zcong_def dvd_def)
   1.677 +  apply (rule_tac x = "a div m - b div m" in exI)
   1.678 +  apply (rule_tac m1 = m in aux [THEN trans])
   1.679 +  apply auto
   1.680 +  done
   1.681 +
   1.682 +lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
   1.683 +  apply (auto simp add: zcong_def)
   1.684 +  done
   1.685 +
   1.686 +lemma zcong_zero [iff]: "[a = b] (mod #0) = (a = b)"
   1.687 +  apply (auto simp add: zcong_def)
   1.688 +  done
   1.689 +
   1.690 +lemma "[a = b] (mod m) = (a mod m = b mod m)"
   1.691 +  apply (tactic {* zdiv_undefined_case_tac "m = #0" 1 *})
   1.692 +  apply (case_tac "#0 < m")
   1.693 +   apply (simp add: zcong_zmod_eq)
   1.694 +  apply (rule_tac t = m in zminus_zminus [THEN subst])
   1.695 +  apply (subst zcong_zminus)
   1.696 +  apply (subst zcong_zmod_eq)
   1.697 +   apply arith
   1.698 +  oops  -- {* FIXME: finish this proof? *}
   1.699 +
   1.700 +
   1.701 +subsection {* Modulo *}
   1.702 +
   1.703 +lemma zmod_zdvd_zmod:
   1.704 +    "#0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
   1.705 +  apply (unfold dvd_def)
   1.706 +  apply auto
   1.707 +  apply (subst zcong_zmod_eq [symmetric])
   1.708 +   prefer 2
   1.709 +   apply (subst zcong_iff_lin)
   1.710 +   apply (rule_tac x = "k * (a div (m * k))" in exI)
   1.711 +   apply (subst zadd_commute)
   1.712 +   apply (subst zmult_assoc [symmetric])
   1.713 +   apply (rule_tac zmod_zdiv_equality)
   1.714 +  apply assumption
   1.715 +  done
   1.716 +
   1.717 +
   1.718 +subsection {* Extended GCD *}
   1.719 +
   1.720 +declare xzgcda.simps [simp del]
   1.721 +
   1.722 +lemma aux1:
   1.723 +  "zgcd (r', r) = k --> #0 < r -->
   1.724 +    (\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn))"
   1.725 +  apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
   1.726 +    z = s and aa = t' and ab = t in xzgcda.induct)
   1.727 +  apply (subst zgcd_eq)
   1.728 +  apply (subst xzgcda.simps)
   1.729 +  apply auto
   1.730 +  apply (case_tac "r' mod r = #0")
   1.731 +   prefer 2
   1.732 +   apply (frule_tac a = "r'" in pos_mod_sign)
   1.733 +   apply auto
   1.734 +   apply arith
   1.735 +  apply (rule exI)
   1.736 +  apply (rule exI)
   1.737 +  apply (subst xzgcda.simps)
   1.738 +  apply auto
   1.739 +  apply (simp add: zabs_def)
   1.740 +  done
   1.741 +
   1.742 +lemma aux2:
   1.743 +  "(\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn)) --> #0 < r -->
   1.744 +    zgcd (r', r) = k"
   1.745 +  apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
   1.746 +    z = s and aa = t' and ab = t in xzgcda.induct)
   1.747 +  apply (subst zgcd_eq)
   1.748 +  apply (subst xzgcda.simps)
   1.749 +  apply (auto simp add: linorder_not_le)
   1.750 +  apply (case_tac "r' mod r = #0")
   1.751 +   prefer 2
   1.752 +   apply (frule_tac a = "r'" in pos_mod_sign)
   1.753 +   apply auto
   1.754 +   apply arith
   1.755 +  apply (erule_tac P = "xzgcda ?u = ?v" in rev_mp)
   1.756 +  apply (subst xzgcda.simps)
   1.757 +  apply auto
   1.758 +  apply (simp add: zabs_def)
   1.759 +  done
   1.760 +
   1.761 +lemma xzgcd_correct:
   1.762 +    "#0 < n ==> (zgcd (m, n) = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
   1.763 +  apply (unfold xzgcd_def)
   1.764 +  apply (rule iffI)
   1.765 +   apply (rule_tac [2] aux2 [THEN mp, THEN mp])
   1.766 +    apply (rule aux1 [THEN mp, THEN mp])
   1.767 +     apply auto
   1.768 +  done
   1.769 +
   1.770 +
   1.771 +text {* \medskip @{term xzgcd} linear *}
   1.772 +
   1.773 +lemma aux:
   1.774 +  "(a - r * b) * m + (c - r * d) * (n::int) =
   1.775 +    (a * m + c * n) - r * (b * m + d * n)"
   1.776 +  apply (simp add: zdiff_zmult_distrib zadd_zmult_distrib2 zmult_assoc)
   1.777 +  done
   1.778 +
   1.779 +lemma aux:
   1.780 +  "r' = s' * m + t' * n ==> r = s * m + t * n
   1.781 +    ==> (r' mod r) = (s' - (r' div r) * s) * m + (t' - (r' div r) * t) * (n::int)"
   1.782 +  apply (rule trans)
   1.783 +   apply (rule_tac [2] aux [symmetric])
   1.784 +  apply simp
   1.785 +  apply (subst eq_zdiff_eq)
   1.786 +  apply (rule trans [symmetric])
   1.787 +  apply (rule_tac b = "s * m + t * n" in zmod_zdiv_equality)
   1.788 +  apply (simp add: zmult_commute)
   1.789 +  done
   1.790 +
   1.791 +lemma order_le_neq_implies_less: "(x::'a::order) \<le> y ==> x \<noteq> y ==> x < y"
   1.792 +  by (rule iffD2 [OF order_less_le conjI])
   1.793 +
   1.794 +lemma xzgcda_linear [rule_format]:
   1.795 +  "#0 < r --> xzgcda (m, n, r', r, s', s, t', t) = (rn, sn, tn) -->
   1.796 +    r' = s' * m + t' * n -->  r = s * m + t * n --> rn = sn * m + tn * n"
   1.797 +  apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
   1.798 +    z = s and aa = t' and ab = t in xzgcda.induct)
   1.799 +  apply (subst xzgcda.simps)
   1.800 +  apply (simp (no_asm))
   1.801 +  apply (rule impI)+
   1.802 +  apply (case_tac "r' mod r = #0")
   1.803 +   apply (simp add: xzgcda.simps)
   1.804 +   apply clarify
   1.805 +  apply (subgoal_tac "#0 < r' mod r")
   1.806 +   apply (rule_tac [2] order_le_neq_implies_less)
   1.807 +   apply (rule_tac [2] pos_mod_sign)
   1.808 +    apply (cut_tac m = m and n = n and r' = r' and r = r and s' = s' and
   1.809 +      s = s and t' = t' and t = t in aux)
   1.810 +      apply auto
   1.811 +  done
   1.812 +
   1.813 +lemma xzgcd_linear:
   1.814 +    "#0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
   1.815 +  apply (unfold xzgcd_def)
   1.816 +  apply (erule xzgcda_linear)
   1.817 +    apply assumption
   1.818 +   apply auto
   1.819 +  done
   1.820 +
   1.821 +lemma zgcd_ex_linear:
   1.822 +    "#0 < n ==> zgcd (m, n) = k ==> (\<exists>s t. k = s * m + t * n)"
   1.823 +  apply (simp add: xzgcd_correct)
   1.824 +  apply safe
   1.825 +  apply (rule exI)+
   1.826 +  apply (erule xzgcd_linear)
   1.827 +  apply auto
   1.828 +  done
   1.829 +
   1.830 +lemma zcong_lineq_ex:
   1.831 +    "#0 < n ==> zgcd (a, n) = #1 ==> \<exists>x. [a * x = #1] (mod n)"
   1.832 +  apply (cut_tac m = a and n = n and k = "#1" in zgcd_ex_linear)
   1.833 +    apply safe
   1.834 +  apply (rule_tac x = s in exI)
   1.835 +  apply (rule_tac b = "s * a + t * n" in zcong_trans)
   1.836 +   prefer 2
   1.837 +   apply simp
   1.838 +  apply (unfold zcong_def)
   1.839 +  apply (simp (no_asm) add: zmult_commute zdvd_zminus_iff)
   1.840 +  done
   1.841 +
   1.842 +lemma zcong_lineq_unique:
   1.843 +  "#0 < n ==>
   1.844 +    zgcd (a, n) = #1 ==> \<exists>!x. #0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
   1.845 +  apply auto
   1.846 +   apply (rule_tac [2] zcong_zless_imp_eq)
   1.847 +       apply (tactic {* stac (thm "zcong_cancel2" RS sym) 6 *})
   1.848 +         apply (rule_tac [8] zcong_trans)
   1.849 +          apply (simp_all (no_asm_simp))
   1.850 +   prefer 2
   1.851 +   apply (simp add: zcong_sym)
   1.852 +  apply (cut_tac a = a and n = n in zcong_lineq_ex)
   1.853 +    apply auto
   1.854 +  apply (rule_tac x = "x * b mod n" in exI)
   1.855 +  apply safe
   1.856 +    apply (simp_all (no_asm_simp) add: pos_mod_bound pos_mod_sign)
   1.857 +  apply (subst zcong_zmod)
   1.858 +  apply (subst zmod_zmult1_eq [symmetric])
   1.859 +  apply (subst zcong_zmod [symmetric])
   1.860 +  apply (subgoal_tac "[a * x * b = #1 * b] (mod n)")
   1.861 +   apply (rule_tac [2] zcong_zmult)
   1.862 +    apply (simp_all add: zmult_assoc)
   1.863 +  done
   1.864  
   1.865  end