1 (* Title: HOL/NumberTheory/IntPrimes.thy
3 Author: Thomas M. Rasmussen
4 Copyright 2000 University of Cambridge
7 header {* Divisibility and prime numbers (on integers) *}
9 theory IntPrimes = Primes:
12 The @{text dvd} relation, GCD, Euclid's extended algorithm, primes,
13 congruences (all on the Integers). Comparable to theory @{text
14 Primes}, but @{text dvd} is included here as it is not present in
15 main HOL. Also includes extended GCD and congruences not present in
20 subsection {* Definitions *}
23 xzgcda :: "int * int * int * int * int * int * int * int => int * int * int"
24 xzgcd :: "int => int => int * int * int"
26 zcong :: "int => int => int => bool" ("(1[_ = _] '(mod _'))")
29 "measure ((\<lambda>(m, n, r', r, s', s, t', t). nat r)
30 :: int * int * int * int *int * int * int * int => nat)"
31 "xzgcda (m, n, r', r, s', s, t', t) =
32 (if r \<le> 0 then (r', s', t')
33 else xzgcda (m, n, r, r' mod r, s, s' - (r' div r) * s, t, t' - (r' div r) * t))"
34 (hints simp: pos_mod_bound)
37 zgcd :: "int * int => int"
38 "zgcd == \<lambda>(x,y). int (gcd (nat (abs x), nat (abs y)))"
41 xzgcd_def: "xzgcd m n == xzgcda (m, n, m, n, 1, 0, 0, 1)"
42 zprime_def: "zprime == {p. 1 < p \<and> (\<forall>m. m dvd p --> m = 1 \<or> m = p)}"
43 zcong_def: "[a = b] (mod m) == m dvd (a - b)"
47 "(abs (z::int) = w) = (z = w \<and> 0 <= z \<or> z = -w \<and> z < 0)"
48 apply (auto simp add: zabs_def)
52 text {* \medskip @{term gcd} lemmas *}
54 lemma gcd_add1_eq: "gcd (m + k, k) = gcd (m + k, m)"
55 apply (simp add: gcd_commute)
58 lemma gcd_diff2: "m \<le> n ==> gcd (n, n - m) = gcd (n, m)"
59 apply (subgoal_tac "n = m + (n - m)")
60 apply (erule ssubst, rule gcd_add1_eq)
65 subsection {* Divides relation *}
67 lemma zdvd_0_right [iff]: "(m::int) dvd 0"
68 apply (unfold dvd_def)
69 apply (blast intro: zmult_0_right [symmetric])
72 lemma zdvd_0_left [iff]: "(0 dvd (m::int)) = (m = 0)"
73 apply (unfold dvd_def)
77 lemma zdvd_1_left [iff]: "1 dvd (m::int)"
78 apply (unfold dvd_def)
82 lemma zdvd_refl [simp]: "m dvd (m::int)"
83 apply (unfold dvd_def)
84 apply (blast intro: zmult_1_right [symmetric])
87 lemma zdvd_trans: "m dvd n ==> n dvd k ==> m dvd (k::int)"
88 apply (unfold dvd_def)
89 apply (blast intro: zmult_assoc)
92 lemma zdvd_zminus_iff: "(m dvd -n) = (m dvd (n::int))"
93 apply (unfold dvd_def)
95 apply (rule_tac [!] x = "-k" in exI)
99 lemma zdvd_zminus2_iff: "(-m dvd n) = (m dvd (n::int))"
100 apply (unfold dvd_def)
102 apply (rule_tac [!] x = "-k" in exI)
107 "0 < m ==> 0 < n ==> m dvd n ==> n dvd m ==> m = (n::int)"
108 apply (unfold dvd_def)
110 apply (simp add: zmult_assoc zmult_eq_self_iff int_0_less_mult_iff zmult_eq_1_iff)
113 lemma zdvd_zadd: "k dvd m ==> k dvd n ==> k dvd (m + n :: int)"
114 apply (unfold dvd_def)
115 apply (blast intro: zadd_zmult_distrib2 [symmetric])
118 lemma zdvd_zdiff: "k dvd m ==> k dvd n ==> k dvd (m - n :: int)"
119 apply (unfold dvd_def)
120 apply (blast intro: zdiff_zmult_distrib2 [symmetric])
123 lemma zdvd_zdiffD: "k dvd m - n ==> k dvd n ==> k dvd (m::int)"
124 apply (subgoal_tac "m = n + (m - n)")
126 apply (blast intro: zdvd_zadd)
130 lemma zdvd_zmult: "k dvd (n::int) ==> k dvd m * n"
131 apply (unfold dvd_def)
132 apply (blast intro: zmult_left_commute)
135 lemma zdvd_zmult2: "k dvd (m::int) ==> k dvd m * n"
136 apply (subst zmult_commute)
137 apply (erule zdvd_zmult)
140 lemma [iff]: "(k::int) dvd m * k"
141 apply (rule zdvd_zmult)
142 apply (rule zdvd_refl)
145 lemma [iff]: "(k::int) dvd k * m"
146 apply (rule zdvd_zmult2)
147 apply (rule zdvd_refl)
150 lemma zdvd_zmultD2: "j * k dvd n ==> j dvd (n::int)"
151 apply (unfold dvd_def)
152 apply (simp add: zmult_assoc)
156 lemma zdvd_zmultD: "j * k dvd n ==> k dvd (n::int)"
157 apply (rule zdvd_zmultD2)
158 apply (subst zmult_commute)
162 lemma zdvd_zmult_mono: "i dvd m ==> j dvd (n::int) ==> i * j dvd m * n"
163 apply (unfold dvd_def)
165 apply (rule_tac x = "k * ka" in exI)
166 apply (simp add: zmult_ac)
169 lemma zdvd_reduce: "(k dvd n + k * m) = (k dvd (n::int))"
171 apply (erule_tac [2] zdvd_zadd)
172 apply (subgoal_tac "n = (n + k * m) - k * m")
174 apply (erule zdvd_zdiff)
178 lemma zdvd_zmod: "f dvd m ==> f dvd (n::int) ==> f dvd m mod n"
179 apply (unfold dvd_def)
180 apply (auto simp add: zmod_zmult_zmult1)
183 lemma zdvd_zmod_imp_zdvd: "k dvd m mod n ==> k dvd n ==> k dvd (m::int)"
184 apply (subgoal_tac "k dvd n * (m div n) + m mod n")
185 apply (simp add: zmod_zdiv_equality [symmetric])
186 apply (simp only: zdvd_zadd zdvd_zmult2)
189 lemma zdvd_iff_zmod_eq_0: "(k dvd n) = (n mod (k::int) = 0)"
190 apply (unfold dvd_def)
194 lemma zdvd_not_zless: "0 < m ==> m < n ==> \<not> n dvd (m::int)"
195 apply (unfold dvd_def)
197 apply (subgoal_tac "0 < n")
199 apply (blast intro: zless_trans)
200 apply (simp add: int_0_less_mult_iff)
201 apply (subgoal_tac "n * k < n * 1")
202 apply (drule zmult_zless_cancel1 [THEN iffD1])
206 lemma int_dvd_iff: "(int m dvd z) = (m dvd nat (abs z))"
207 apply (auto simp add: dvd_def nat_abs_mult_distrib)
208 apply (auto simp add: nat_eq_iff zabs_eq_iff)
209 apply (rule_tac [2] x = "-(int k)" in exI)
210 apply (auto simp add: zmult_int [symmetric])
213 lemma dvd_int_iff: "(z dvd int m) = (nat (abs z) dvd m)"
214 apply (auto simp add: dvd_def zabs_def zmult_int [symmetric])
215 apply (rule_tac [3] x = "nat k" in exI)
216 apply (rule_tac [2] x = "-(int k)" in exI)
217 apply (rule_tac x = "nat (-k)" in exI)
218 apply (cut_tac [3] k = m in int_less_0_conv)
219 apply (cut_tac k = m in int_less_0_conv)
220 apply (auto simp add: int_0_le_mult_iff zmult_less_0_iff
221 nat_mult_distrib [symmetric] nat_eq_iff2)
224 lemma nat_dvd_iff: "(nat z dvd m) = (if 0 \<le> z then (z dvd int m) else m = 0)"
225 apply (auto simp add: dvd_def zmult_int [symmetric])
226 apply (rule_tac x = "nat k" in exI)
227 apply (cut_tac k = m in int_less_0_conv)
228 apply (auto simp add: int_0_le_mult_iff zmult_less_0_iff
229 nat_mult_distrib [symmetric] nat_eq_iff2)
232 lemma zminus_dvd_iff [iff]: "(-z dvd w) = (z dvd (w::int))"
233 apply (auto simp add: dvd_def)
234 apply (rule_tac [!] x = "-k" in exI)
238 lemma dvd_zminus_iff [iff]: "(z dvd -w) = (z dvd (w::int))"
239 apply (auto simp add: dvd_def)
240 apply (drule zminus_equation [THEN iffD1])
241 apply (rule_tac [!] x = "-k" in exI)
246 subsection {* Euclid's Algorithm and GCD *}
248 lemma zgcd_0 [simp]: "zgcd (m, 0) = abs m"
249 apply (simp add: zgcd_def zabs_def)
252 lemma zgcd_0_left [simp]: "zgcd (0, m) = abs m"
253 apply (simp add: zgcd_def zabs_def)
256 lemma zgcd_zminus [simp]: "zgcd (-m, n) = zgcd (m, n)"
257 apply (simp add: zgcd_def)
260 lemma zgcd_zminus2 [simp]: "zgcd (m, -n) = zgcd (m, n)"
261 apply (simp add: zgcd_def)
264 lemma zgcd_non_0: "0 < n ==> zgcd (m, n) = zgcd (n, m mod n)"
265 apply (frule_tac b = n and a = m in pos_mod_sign)
266 apply (simp add: zgcd_def zabs_def nat_mod_distrib)
267 apply (auto simp add: gcd_non_0 nat_mod_distrib [symmetric] zmod_zminus1_eq_if)
268 apply (frule_tac a = m in pos_mod_bound)
269 apply (simp add: nat_diff_distrib gcd_diff2 nat_le_eq_zle)
270 apply (simp add: gcd_non_0 nat_mod_distrib [symmetric])
273 lemma zgcd_eq: "zgcd (m, n) = zgcd (n, m mod n)"
274 apply (case_tac "n = 0", simp add: DIVISION_BY_ZERO)
275 apply (auto simp add: linorder_neq_iff zgcd_non_0)
276 apply (cut_tac m = "-m" and n = "-n" in zgcd_non_0)
280 lemma zgcd_1 [simp]: "zgcd (m, 1) = 1"
281 apply (simp add: zgcd_def zabs_def)
284 lemma zgcd_0_1_iff [simp]: "(zgcd (0, m) = 1) = (abs m = 1)"
285 apply (simp add: zgcd_def zabs_def)
288 lemma zgcd_zdvd1 [iff]: "zgcd (m, n) dvd m"
289 apply (simp add: zgcd_def zabs_def int_dvd_iff)
292 lemma zgcd_zdvd2 [iff]: "zgcd (m, n) dvd n"
293 apply (simp add: zgcd_def zabs_def int_dvd_iff)
296 lemma zgcd_greatest_iff: "k dvd zgcd (m, n) = (k dvd m \<and> k dvd n)"
297 apply (simp add: zgcd_def zabs_def int_dvd_iff dvd_int_iff nat_dvd_iff)
300 lemma zgcd_commute: "zgcd (m, n) = zgcd (n, m)"
301 apply (simp add: zgcd_def gcd_commute)
304 lemma zgcd_1_left [simp]: "zgcd (1, m) = 1"
305 apply (simp add: zgcd_def gcd_1_left)
308 lemma zgcd_assoc: "zgcd (zgcd (k, m), n) = zgcd (k, zgcd (m, n))"
309 apply (simp add: zgcd_def gcd_assoc)
312 lemma zgcd_left_commute: "zgcd (k, zgcd (m, n)) = zgcd (m, zgcd (k, n))"
313 apply (rule zgcd_commute [THEN trans])
314 apply (rule zgcd_assoc [THEN trans])
315 apply (rule zgcd_commute [THEN arg_cong])
318 lemmas zgcd_ac = zgcd_assoc zgcd_commute zgcd_left_commute
319 -- {* addition is an AC-operator *}
321 lemma zgcd_zmult_distrib2: "0 \<le> k ==> k * zgcd (m, n) = zgcd (k * m, k * n)"
322 apply (simp del: zmult_zminus_right
323 add: zmult_zminus_right [symmetric] nat_mult_distrib zgcd_def zabs_def
324 zmult_less_0_iff gcd_mult_distrib2 [symmetric] zmult_int [symmetric])
327 lemma zgcd_zmult_distrib2_abs: "zgcd (k * m, k * n) = abs k * zgcd (m, n)"
328 apply (simp add: zabs_def zgcd_zmult_distrib2)
331 lemma zgcd_self [simp]: "0 \<le> m ==> zgcd (m, m) = m"
332 apply (cut_tac k = m and m = "1" and n = "1" in zgcd_zmult_distrib2)
336 lemma zgcd_zmult_eq_self [simp]: "0 \<le> k ==> zgcd (k, k * n) = k"
337 apply (cut_tac k = k and m = "1" and n = n in zgcd_zmult_distrib2)
341 lemma zgcd_zmult_eq_self2 [simp]: "0 \<le> k ==> zgcd (k * n, k) = k"
342 apply (cut_tac k = k and m = n and n = "1" in zgcd_zmult_distrib2)
346 lemma zrelprime_zdvd_zmult_aux: "zgcd (n, k) = 1 ==> k dvd m * n ==> 0 \<le> m ==> k dvd m"
347 apply (subgoal_tac "m = zgcd (m * n, m * k)")
348 apply (erule ssubst, rule zgcd_greatest_iff [THEN iffD2])
349 apply (simp_all add: zgcd_zmult_distrib2 [symmetric] int_0_le_mult_iff)
352 lemma zrelprime_zdvd_zmult: "zgcd (n, k) = 1 ==> k dvd m * n ==> k dvd m"
353 apply (case_tac "0 \<le> m")
354 apply (blast intro: zrelprime_zdvd_zmult_aux)
355 apply (subgoal_tac "k dvd -m")
356 apply (rule_tac [2] zrelprime_zdvd_zmult_aux)
360 lemma zprime_imp_zrelprime:
361 "p \<in> zprime ==> \<not> p dvd n ==> zgcd (n, p) = 1"
362 apply (unfold zprime_def)
366 lemma zless_zprime_imp_zrelprime:
367 "p \<in> zprime ==> 0 < n ==> n < p ==> zgcd (n, p) = 1"
368 apply (erule zprime_imp_zrelprime)
369 apply (erule zdvd_not_zless)
373 lemma zprime_zdvd_zmult:
374 "0 \<le> (m::int) ==> p \<in> zprime ==> p dvd m * n ==> p dvd m \<or> p dvd n"
376 apply (rule zrelprime_zdvd_zmult)
377 apply (rule zprime_imp_zrelprime)
381 lemma zgcd_zadd_zmult [simp]: "zgcd (m + n * k, n) = zgcd (m, n)"
382 apply (rule zgcd_eq [THEN trans])
383 apply (simp add: zmod_zadd1_eq)
384 apply (rule zgcd_eq [symmetric])
387 lemma zgcd_zdvd_zgcd_zmult: "zgcd (m, n) dvd zgcd (k * m, n)"
388 apply (simp add: zgcd_greatest_iff)
389 apply (blast intro: zdvd_trans)
392 lemma zgcd_zmult_zdvd_zgcd:
393 "zgcd (k, n) = 1 ==> zgcd (k * m, n) dvd zgcd (m, n)"
394 apply (simp add: zgcd_greatest_iff)
395 apply (rule_tac n = k in zrelprime_zdvd_zmult)
397 apply (simp add: zmult_commute)
398 apply (subgoal_tac "zgcd (k, zgcd (k * m, n)) = zgcd (k * m, zgcd (k, n))")
400 apply (simp (no_asm) add: zgcd_ac)
403 lemma zgcd_zmult_cancel: "zgcd (k, n) = 1 ==> zgcd (k * m, n) = zgcd (m, n)"
404 apply (simp add: zgcd_def nat_abs_mult_distrib gcd_mult_cancel)
407 lemma zgcd_zgcd_zmult:
408 "zgcd (k, m) = 1 ==> zgcd (n, m) = 1 ==> zgcd (k * n, m) = 1"
409 apply (simp (no_asm_simp) add: zgcd_zmult_cancel)
412 lemma zdvd_iff_zgcd: "0 < m ==> (m dvd n) = (zgcd (n, m) = m)"
414 apply (rule_tac [2] n = "zgcd (n, m)" in zdvd_trans)
415 apply (rule_tac [3] zgcd_zdvd1)
417 apply (unfold dvd_def)
422 subsection {* Congruences *}
424 lemma zcong_1 [simp]: "[a = b] (mod 1)"
425 apply (unfold zcong_def)
429 lemma zcong_refl [simp]: "[k = k] (mod m)"
430 apply (unfold zcong_def)
434 lemma zcong_sym: "[a = b] (mod m) = [b = a] (mod m)"
435 apply (unfold zcong_def dvd_def)
437 apply (rule_tac [!] x = "-k" in exI)
442 "[a = b] (mod m) ==> [c = d] (mod m) ==> [a + c = b + d] (mod m)"
443 apply (unfold zcong_def)
444 apply (rule_tac s = "(a - b) + (c - d)" in subst)
445 apply (rule_tac [2] zdvd_zadd)
450 "[a = b] (mod m) ==> [c = d] (mod m) ==> [a - c = b - d] (mod m)"
451 apply (unfold zcong_def)
452 apply (rule_tac s = "(a - b) - (c - d)" in subst)
453 apply (rule_tac [2] zdvd_zdiff)
458 "[a = b] (mod m) ==> [b = c] (mod m) ==> [a = c] (mod m)"
459 apply (unfold zcong_def dvd_def)
461 apply (rule_tac x = "k + ka" in exI)
462 apply (simp add: zadd_ac zadd_zmult_distrib2)
466 "[a = b] (mod m) ==> [c = d] (mod m) ==> [a * c = b * d] (mod m)"
467 apply (rule_tac b = "b * c" in zcong_trans)
468 apply (unfold zcong_def)
469 apply (rule_tac s = "c * (a - b)" in subst)
470 apply (rule_tac [3] s = "b * (c - d)" in subst)
472 apply (blast intro: zdvd_zmult)
474 apply (blast intro: zdvd_zmult)
475 apply (simp_all add: zdiff_zmult_distrib2 zmult_commute)
478 lemma zcong_scalar: "[a = b] (mod m) ==> [a * k = b * k] (mod m)"
479 apply (rule zcong_zmult)
483 lemma zcong_scalar2: "[a = b] (mod m) ==> [k * a = k * b] (mod m)"
484 apply (rule zcong_zmult)
488 lemma zcong_zmult_self: "[a * m = b * m] (mod m)"
489 apply (unfold zcong_def)
490 apply (rule zdvd_zdiff)
495 "p \<in> zprime ==> 0 < a ==> [a * a = 1] (mod p)
496 ==> [a = 1] (mod p) \<or> [a = p - 1] (mod p)"
497 apply (unfold zcong_def)
498 apply (rule zprime_zdvd_zmult)
499 apply (rule_tac [3] s = "a * a - 1 + p * (1 - a)" in subst)
501 apply (simp add: zdvd_reduce)
502 apply (simp_all add: zdiff_zmult_distrib zmult_commute zdiff_zmult_distrib2)
507 zgcd (k, m) = 1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
510 apply (blast intro: zcong_scalar)
511 apply (case_tac "b < a")
513 apply (subst zcong_sym)
514 apply (unfold zcong_def)
515 apply (rule_tac [!] zrelprime_zdvd_zmult)
516 apply (simp_all add: zdiff_zmult_distrib)
517 apply (subgoal_tac "m dvd (-(a * k - b * k))")
518 apply (simp add: zminus_zdiff_eq)
519 apply (subst zdvd_zminus_iff)
525 zgcd (k, m) = 1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
526 apply (simp add: zmult_commute zcong_cancel)
529 lemma zcong_zgcd_zmult_zmod:
530 "[a = b] (mod m) ==> [a = b] (mod n) ==> zgcd (m, n) = 1
531 ==> [a = b] (mod m * n)"
532 apply (unfold zcong_def dvd_def)
534 apply (subgoal_tac "m dvd n * ka")
535 apply (subgoal_tac "m dvd ka")
536 apply (case_tac [2] "0 \<le> ka")
538 apply (subst zdvd_zminus_iff [symmetric])
539 apply (rule_tac n = n in zrelprime_zdvd_zmult)
540 apply (simp add: zgcd_commute)
541 apply (simp add: zmult_commute zdvd_zminus_iff)
543 apply (rule_tac n = n in zrelprime_zdvd_zmult)
544 apply (simp add: zgcd_commute)
545 apply (simp add: zmult_commute)
546 apply (auto simp add: dvd_def)
547 apply (blast intro: sym)
550 lemma zcong_zless_imp_eq:
552 a < m ==> 0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
553 apply (unfold zcong_def dvd_def)
555 apply (drule_tac f = "\<lambda>z. z mod m" in arg_cong)
556 apply (cut_tac z = a and w = b in zless_linear)
558 apply (subgoal_tac [2] "(a - b) mod m = a - b")
559 apply (rule_tac [3] mod_pos_pos_trivial)
561 apply (subgoal_tac "(m + (a - b)) mod m = m + (a - b)")
562 apply (rule_tac [2] mod_pos_pos_trivial)
566 lemma zcong_square_zless:
567 "p \<in> zprime ==> 0 < a ==> a < p ==>
568 [a * a = 1] (mod p) ==> a = 1 \<or> a = p - 1"
569 apply (cut_tac p = p and a = a in zcong_square)
570 apply (simp add: zprime_def)
571 apply (auto intro: zcong_zless_imp_eq)
575 "0 < a ==> a < m ==> 0 < b ==> b < a ==> \<not> [a = b] (mod m)"
576 apply (unfold zcong_def)
577 apply (rule zdvd_not_zless)
582 "0 \<le> a ==> a < m ==> [a = 0] (mod m) ==> a = 0"
583 apply (unfold zcong_def dvd_def)
585 apply (subgoal_tac "0 < m")
586 apply (rotate_tac -1)
587 apply (simp add: int_0_le_mult_iff)
588 apply (subgoal_tac "m * k < m * 1")
589 apply (drule zmult_zless_cancel1 [THEN iffD1])
590 apply (auto simp add: linorder_neq_iff)
593 lemma zcong_zless_unique:
594 "0 < m ==> (\<exists>!b. 0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
596 apply (subgoal_tac [2] "[b = y] (mod m)")
597 apply (case_tac [2] "b = 0")
598 apply (case_tac [3] "y = 0")
599 apply (auto intro: zcong_trans zcong_zless_0 zcong_zless_imp_eq order_less_le
601 apply (unfold zcong_def dvd_def)
602 apply (rule_tac x = "a mod m" in exI)
603 apply (auto simp add: pos_mod_sign pos_mod_bound)
604 apply (rule_tac x = "-(a div m)" in exI)
605 apply (simp add:zdiff_eq_eq eq_zdiff_eq zadd_commute)
608 lemma zcong_iff_lin: "([a = b] (mod m)) = (\<exists>k. b = a + m * k)"
609 apply (unfold zcong_def dvd_def)
611 apply (rule_tac [!] x = "-k" in exI)
615 lemma zgcd_zcong_zgcd:
617 zgcd (a, m) = 1 ==> [a = b] (mod m) ==> zgcd (b, m) = 1"
618 apply (auto simp add: zcong_iff_lin)
621 lemma zcong_zmod_aux: "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
622 by(simp add: zdiff_zmult_distrib2 zadd_zdiff_eq eq_zdiff_eq zadd_ac)
624 lemma zcong_zmod: "[a = b] (mod m) = [a mod m = b mod m] (mod m)"
625 apply (unfold zcong_def)
626 apply (rule_tac t = "a - b" in ssubst)
627 apply (rule_tac "m" = "m" in zcong_zmod_aux)
629 apply (rule_tac [2] k = m and m = "a div m - b div m" in zdvd_reduce)
630 apply (simp add: zadd_commute)
633 lemma zcong_zmod_eq: "0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
635 apply (rule_tac m = m in zcong_zless_imp_eq)
637 apply (subst zcong_zmod [symmetric])
638 apply (simp_all add: pos_mod_bound pos_mod_sign)
639 apply (unfold zcong_def dvd_def)
640 apply (rule_tac x = "a div m - b div m" in exI)
641 apply (rule_tac m1 = m in zcong_zmod_aux [THEN trans])
645 lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
646 apply (auto simp add: zcong_def)
649 lemma zcong_zero [iff]: "[a = b] (mod 0) = (a = b)"
650 apply (auto simp add: zcong_def)
653 lemma "[a = b] (mod m) = (a mod m = b mod m)"
654 apply (case_tac "m = 0", simp add: DIVISION_BY_ZERO)
655 apply (simp add: linorder_neq_iff)
657 prefer 2 apply (simp add: zcong_zmod_eq)
658 txt{*Remainding case: @{term "m<0"}*}
659 apply (rule_tac t = m in zminus_zminus [THEN subst])
660 apply (subst zcong_zminus)
661 apply (subst zcong_zmod_eq)
663 apply (frule neg_mod_bound [of _ a], frule neg_mod_bound [of _ b])
664 apply (simp add: zmod_zminus2_eq_if)
667 subsection {* Modulo *}
669 lemma zmod_zdvd_zmod:
670 "0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
671 apply (unfold dvd_def)
673 apply (subst zcong_zmod_eq [symmetric])
675 apply (subst zcong_iff_lin)
676 apply (rule_tac x = "k * (a div (m * k))" in exI)
677 apply(simp add:zmult_assoc [symmetric])
682 subsection {* Extended GCD *}
684 declare xzgcda.simps [simp del]
686 lemma xzgcd_correct_aux1:
687 "zgcd (r', r) = k --> 0 < r -->
688 (\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn))"
689 apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
690 z = s and aa = t' and ab = t in xzgcda.induct)
691 apply (subst zgcd_eq)
692 apply (subst xzgcda.simps)
694 apply (case_tac "r' mod r = 0")
696 apply (frule_tac a = "r'" in pos_mod_sign)
700 apply (subst xzgcda.simps)
702 apply (simp add: zabs_def)
705 lemma xzgcd_correct_aux2:
706 "(\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn)) --> 0 < r -->
708 apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
709 z = s and aa = t' and ab = t in xzgcda.induct)
710 apply (subst zgcd_eq)
711 apply (subst xzgcda.simps)
712 apply (auto simp add: linorder_not_le)
713 apply (case_tac "r' mod r = 0")
715 apply (frule_tac a = "r'" in pos_mod_sign)
717 apply (erule_tac P = "xzgcda ?u = ?v" in rev_mp)
718 apply (subst xzgcda.simps)
720 apply (simp add: zabs_def)
724 "0 < n ==> (zgcd (m, n) = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
725 apply (unfold xzgcd_def)
727 apply (rule_tac [2] xzgcd_correct_aux2 [THEN mp, THEN mp])
728 apply (rule xzgcd_correct_aux1 [THEN mp, THEN mp])
733 text {* \medskip @{term xzgcd} linear *}
735 lemma xzgcda_linear_aux1:
736 "(a - r * b) * m + (c - r * d) * (n::int) =
737 (a * m + c * n) - r * (b * m + d * n)"
738 apply (simp add: zdiff_zmult_distrib zadd_zmult_distrib2 zmult_assoc)
741 lemma xzgcda_linear_aux2:
742 "r' = s' * m + t' * n ==> r = s * m + t * n
743 ==> (r' mod r) = (s' - (r' div r) * s) * m + (t' - (r' div r) * t) * (n::int)"
745 apply (rule_tac [2] xzgcda_linear_aux1 [symmetric])
746 apply (simp add: eq_zdiff_eq zmult_commute)
749 lemma order_le_neq_implies_less: "(x::'a::order) \<le> y ==> x \<noteq> y ==> x < y"
750 by (rule iffD2 [OF order_less_le conjI])
752 lemma xzgcda_linear [rule_format]:
753 "0 < r --> xzgcda (m, n, r', r, s', s, t', t) = (rn, sn, tn) -->
754 r' = s' * m + t' * n --> r = s * m + t * n --> rn = sn * m + tn * n"
755 apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
756 z = s and aa = t' and ab = t in xzgcda.induct)
757 apply (subst xzgcda.simps)
758 apply (simp (no_asm))
760 apply (case_tac "r' mod r = 0")
761 apply (simp add: xzgcda.simps)
763 apply (subgoal_tac "0 < r' mod r")
764 apply (rule_tac [2] order_le_neq_implies_less)
765 apply (rule_tac [2] pos_mod_sign)
766 apply (cut_tac m = m and n = n and r' = r' and r = r and s' = s' and
767 s = s and t' = t' and t = t in xzgcda_linear_aux2)
772 "0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
773 apply (unfold xzgcd_def)
774 apply (erule xzgcda_linear)
779 lemma zgcd_ex_linear:
780 "0 < n ==> zgcd (m, n) = k ==> (\<exists>s t. k = s * m + t * n)"
781 apply (simp add: xzgcd_correct)
784 apply (erule xzgcd_linear)
788 lemma zcong_lineq_ex:
789 "0 < n ==> zgcd (a, n) = 1 ==> \<exists>x. [a * x = 1] (mod n)"
790 apply (cut_tac m = a and n = n and k = "1" in zgcd_ex_linear)
792 apply (rule_tac x = s in exI)
793 apply (rule_tac b = "s * a + t * n" in zcong_trans)
796 apply (unfold zcong_def)
797 apply (simp (no_asm) add: zmult_commute zdvd_zminus_iff)
800 lemma zcong_lineq_unique:
802 zgcd (a, n) = 1 ==> \<exists>!x. 0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
804 apply (rule_tac [2] zcong_zless_imp_eq)
805 apply (tactic {* stac (thm "zcong_cancel2" RS sym) 6 *})
806 apply (rule_tac [8] zcong_trans)
807 apply (simp_all (no_asm_simp))
809 apply (simp add: zcong_sym)
810 apply (cut_tac a = a and n = n in zcong_lineq_ex)
812 apply (rule_tac x = "x * b mod n" in exI)
814 apply (simp_all (no_asm_simp) add: pos_mod_bound pos_mod_sign)
815 apply (subst zcong_zmod)
816 apply (subst zmod_zmult1_eq [symmetric])
817 apply (subst zcong_zmod [symmetric])
818 apply (subgoal_tac "[a * x * b = 1 * b] (mod n)")
819 apply (rule_tac [2] zcong_zmult)
820 apply (simp_all add: zmult_assoc)