src/HOL/NumberTheory/IntPrimes.thy
 author nipkow Wed Aug 18 11:09:40 2004 +0200 (2004-08-18) changeset 15140 322485b816ac parent 15003 6145dd7538d7 child 15229 1eb23f805c06 permissions -rw-r--r--
import -> imports
```     1 (*  Title:      HOL/NumberTheory/IntPrimes.thy
```
```     2     ID:         \$Id\$
```
```     3     Author:     Thomas M. Rasmussen
```
```     4     Copyright   2000  University of Cambridge
```
```     5
```
```     6 Changes by Jeremy Avigad, 2003/02/21:
```
```     7    Repaired definition of zprime_def, added "0 <= m &"
```
```     8    Added lemma zgcd_geq_zero
```
```     9    Repaired proof of zprime_imp_zrelprime
```
```    10 *)
```
```    11
```
```    12 header {* Divisibility and prime numbers (on integers) *}
```
```    13
```
```    14 theory IntPrimes = Primes:
```
```    15
```
```    16 text {*
```
```    17   The @{text dvd} relation, GCD, Euclid's extended algorithm, primes,
```
```    18   congruences (all on the Integers).  Comparable to theory @{text
```
```    19   Primes}, but @{text dvd} is included here as it is not present in
```
```    20   main HOL.  Also includes extended GCD and congruences not present in
```
```    21   @{text Primes}.
```
```    22 *}
```
```    23
```
```    24
```
```    25 subsection {* Definitions *}
```
```    26
```
```    27 consts
```
```    28   xzgcda :: "int * int * int * int * int * int * int * int => int * int * int"
```
```    29
```
```    30 recdef xzgcda
```
```    31   "measure ((\<lambda>(m, n, r', r, s', s, t', t). nat r)
```
```    32     :: int * int * int * int *int * int * int * int => nat)"
```
```    33   "xzgcda (m, n, r', r, s', s, t', t) =
```
```    34 	(if r \<le> 0 then (r', s', t')
```
```    35 	 else xzgcda (m, n, r, r' mod r,
```
```    36 		      s, s' - (r' div r) * s,
```
```    37 		      t, t' - (r' div r) * t))"
```
```    38
```
```    39 constdefs
```
```    40   zgcd :: "int * int => int"
```
```    41   "zgcd == \<lambda>(x,y). int (gcd (nat (abs x), nat (abs y)))"
```
```    42
```
```    43   zprime :: "int set"
```
```    44   "zprime == {p. 1 < p \<and> (\<forall>m. 0 <= m & m dvd p --> m = 1 \<or> m = p)}"
```
```    45
```
```    46   xzgcd :: "int => int => int * int * int"
```
```    47   "xzgcd m n == xzgcda (m, n, m, n, 1, 0, 0, 1)"
```
```    48
```
```    49   zcong :: "int => int => int => bool"    ("(1[_ = _] '(mod _'))")
```
```    50   "[a = b] (mod m) == m dvd (a - b)"
```
```    51
```
```    52
```
```    53
```
```    54 text {* \medskip @{term gcd} lemmas *}
```
```    55
```
```    56 lemma gcd_add1_eq: "gcd (m + k, k) = gcd (m + k, m)"
```
```    57   by (simp add: gcd_commute)
```
```    58
```
```    59 lemma gcd_diff2: "m \<le> n ==> gcd (n, n - m) = gcd (n, m)"
```
```    60   apply (subgoal_tac "n = m + (n - m)")
```
```    61    apply (erule ssubst, rule gcd_add1_eq, simp)
```
```    62   done
```
```    63
```
```    64
```
```    65 subsection {* Euclid's Algorithm and GCD *}
```
```    66
```
```    67 lemma zgcd_0 [simp]: "zgcd (m, 0) = abs m"
```
```    68   by (simp add: zgcd_def abs_if)
```
```    69
```
```    70 lemma zgcd_0_left [simp]: "zgcd (0, m) = abs m"
```
```    71   by (simp add: zgcd_def abs_if)
```
```    72
```
```    73 lemma zgcd_zminus [simp]: "zgcd (-m, n) = zgcd (m, n)"
```
```    74   by (simp add: zgcd_def)
```
```    75
```
```    76 lemma zgcd_zminus2 [simp]: "zgcd (m, -n) = zgcd (m, n)"
```
```    77   by (simp add: zgcd_def)
```
```    78
```
```    79 lemma zgcd_non_0: "0 < n ==> zgcd (m, n) = zgcd (n, m mod n)"
```
```    80   apply (frule_tac b = n and a = m in pos_mod_sign)
```
```    81   apply (simp del: pos_mod_sign add: zgcd_def abs_if nat_mod_distrib)
```
```    82   apply (auto simp add: gcd_non_0 nat_mod_distrib [symmetric] zmod_zminus1_eq_if)
```
```    83   apply (frule_tac a = m in pos_mod_bound)
```
```    84   apply (simp del: pos_mod_bound add: nat_diff_distrib gcd_diff2 nat_le_eq_zle)
```
```    85   done
```
```    86
```
```    87 lemma zgcd_eq: "zgcd (m, n) = zgcd (n, m mod n)"
```
```    88   apply (case_tac "n = 0", simp add: DIVISION_BY_ZERO)
```
```    89   apply (auto simp add: linorder_neq_iff zgcd_non_0)
```
```    90   apply (cut_tac m = "-m" and n = "-n" in zgcd_non_0, auto)
```
```    91   done
```
```    92
```
```    93 lemma zgcd_1 [simp]: "zgcd (m, 1) = 1"
```
```    94   by (simp add: zgcd_def abs_if)
```
```    95
```
```    96 lemma zgcd_0_1_iff [simp]: "(zgcd (0, m) = 1) = (abs m = 1)"
```
```    97   by (simp add: zgcd_def abs_if)
```
```    98
```
```    99 lemma zgcd_zdvd1 [iff]: "zgcd (m, n) dvd m"
```
```   100   by (simp add: zgcd_def abs_if int_dvd_iff)
```
```   101
```
```   102 lemma zgcd_zdvd2 [iff]: "zgcd (m, n) dvd n"
```
```   103   by (simp add: zgcd_def abs_if int_dvd_iff)
```
```   104
```
```   105 lemma zgcd_greatest_iff: "k dvd zgcd (m, n) = (k dvd m \<and> k dvd n)"
```
```   106   by (simp add: zgcd_def abs_if int_dvd_iff dvd_int_iff nat_dvd_iff)
```
```   107
```
```   108 lemma zgcd_commute: "zgcd (m, n) = zgcd (n, m)"
```
```   109   by (simp add: zgcd_def gcd_commute)
```
```   110
```
```   111 lemma zgcd_1_left [simp]: "zgcd (1, m) = 1"
```
```   112   by (simp add: zgcd_def gcd_1_left)
```
```   113
```
```   114 lemma zgcd_assoc: "zgcd (zgcd (k, m), n) = zgcd (k, zgcd (m, n))"
```
```   115   by (simp add: zgcd_def gcd_assoc)
```
```   116
```
```   117 lemma zgcd_left_commute: "zgcd (k, zgcd (m, n)) = zgcd (m, zgcd (k, n))"
```
```   118   apply (rule zgcd_commute [THEN trans])
```
```   119   apply (rule zgcd_assoc [THEN trans])
```
```   120   apply (rule zgcd_commute [THEN arg_cong])
```
```   121   done
```
```   122
```
```   123 lemmas zgcd_ac = zgcd_assoc zgcd_commute zgcd_left_commute
```
```   124   -- {* addition is an AC-operator *}
```
```   125
```
```   126 lemma zgcd_zmult_distrib2: "0 \<le> k ==> k * zgcd (m, n) = zgcd (k * m, k * n)"
```
```   127   by (simp del: minus_mult_right [symmetric]
```
```   128       add: minus_mult_right nat_mult_distrib zgcd_def abs_if
```
```   129           mult_less_0_iff gcd_mult_distrib2 [symmetric] zmult_int [symmetric])
```
```   130
```
```   131 lemma zgcd_zmult_distrib2_abs: "zgcd (k * m, k * n) = abs k * zgcd (m, n)"
```
```   132   by (simp add: abs_if zgcd_zmult_distrib2)
```
```   133
```
```   134 lemma zgcd_self [simp]: "0 \<le> m ==> zgcd (m, m) = m"
```
```   135   by (cut_tac k = m and m = 1 and n = 1 in zgcd_zmult_distrib2, simp_all)
```
```   136
```
```   137 lemma zgcd_zmult_eq_self [simp]: "0 \<le> k ==> zgcd (k, k * n) = k"
```
```   138   by (cut_tac k = k and m = 1 and n = n in zgcd_zmult_distrib2, simp_all)
```
```   139
```
```   140 lemma zgcd_zmult_eq_self2 [simp]: "0 \<le> k ==> zgcd (k * n, k) = k"
```
```   141   by (cut_tac k = k and m = n and n = 1 in zgcd_zmult_distrib2, simp_all)
```
```   142
```
```   143 lemma zrelprime_zdvd_zmult_aux:
```
```   144      "zgcd (n, k) = 1 ==> k dvd m * n ==> 0 \<le> m ==> k dvd m"
```
```   145   apply (subgoal_tac "m = zgcd (m * n, m * k)")
```
```   146    apply (erule ssubst, rule zgcd_greatest_iff [THEN iffD2])
```
```   147    apply (simp_all add: zgcd_zmult_distrib2 [symmetric] zero_le_mult_iff)
```
```   148   done
```
```   149
```
```   150 lemma zrelprime_zdvd_zmult: "zgcd (n, k) = 1 ==> k dvd m * n ==> k dvd m"
```
```   151   apply (case_tac "0 \<le> m")
```
```   152    apply (blast intro: zrelprime_zdvd_zmult_aux)
```
```   153   apply (subgoal_tac "k dvd -m")
```
```   154    apply (rule_tac [2] zrelprime_zdvd_zmult_aux, auto)
```
```   155   done
```
```   156
```
```   157 lemma zgcd_geq_zero: "0 <= zgcd(x,y)"
```
```   158   by (auto simp add: zgcd_def)
```
```   159
```
```   160 text{*This is merely a sanity check on zprime, since the previous version
```
```   161       denoted the empty set.*}
```
```   162 lemma "2 \<in> zprime"
```
```   163   apply (auto simp add: zprime_def)
```
```   164   apply (frule zdvd_imp_le, simp)
```
```   165   apply (auto simp add: order_le_less dvd_def)
```
```   166   done
```
```   167
```
```   168 lemma zprime_imp_zrelprime:
```
```   169     "p \<in> zprime ==> \<not> p dvd n ==> zgcd (n, p) = 1"
```
```   170   apply (auto simp add: zprime_def)
```
```   171   apply (drule_tac x = "zgcd(n, p)" in allE)
```
```   172   apply (auto simp add: zgcd_zdvd2 [of n p] zgcd_geq_zero)
```
```   173   apply (insert zgcd_zdvd1 [of n p], auto)
```
```   174   done
```
```   175
```
```   176 lemma zless_zprime_imp_zrelprime:
```
```   177     "p \<in> zprime ==> 0 < n ==> n < p ==> zgcd (n, p) = 1"
```
```   178   apply (erule zprime_imp_zrelprime)
```
```   179   apply (erule zdvd_not_zless, assumption)
```
```   180   done
```
```   181
```
```   182 lemma zprime_zdvd_zmult:
```
```   183     "0 \<le> (m::int) ==> p \<in> zprime ==> p dvd m * n ==> p dvd m \<or> p dvd n"
```
```   184   apply safe
```
```   185   apply (rule zrelprime_zdvd_zmult)
```
```   186    apply (rule zprime_imp_zrelprime, auto)
```
```   187   done
```
```   188
```
```   189 lemma zgcd_zadd_zmult [simp]: "zgcd (m + n * k, n) = zgcd (m, n)"
```
```   190   apply (rule zgcd_eq [THEN trans])
```
```   191   apply (simp add: zmod_zadd1_eq)
```
```   192   apply (rule zgcd_eq [symmetric])
```
```   193   done
```
```   194
```
```   195 lemma zgcd_zdvd_zgcd_zmult: "zgcd (m, n) dvd zgcd (k * m, n)"
```
```   196   apply (simp add: zgcd_greatest_iff)
```
```   197   apply (blast intro: zdvd_trans)
```
```   198   done
```
```   199
```
```   200 lemma zgcd_zmult_zdvd_zgcd:
```
```   201     "zgcd (k, n) = 1 ==> zgcd (k * m, n) dvd zgcd (m, n)"
```
```   202   apply (simp add: zgcd_greatest_iff)
```
```   203   apply (rule_tac n = k in zrelprime_zdvd_zmult)
```
```   204    prefer 2
```
```   205    apply (simp add: zmult_commute)
```
```   206   apply (subgoal_tac "zgcd (k, zgcd (k * m, n)) = zgcd (k * m, zgcd (k, n))")
```
```   207    apply simp
```
```   208   apply (simp (no_asm) add: zgcd_ac)
```
```   209   done
```
```   210
```
```   211 lemma zgcd_zmult_cancel: "zgcd (k, n) = 1 ==> zgcd (k * m, n) = zgcd (m, n)"
```
```   212   by (simp add: zgcd_def nat_abs_mult_distrib gcd_mult_cancel)
```
```   213
```
```   214 lemma zgcd_zgcd_zmult:
```
```   215     "zgcd (k, m) = 1 ==> zgcd (n, m) = 1 ==> zgcd (k * n, m) = 1"
```
```   216   by (simp add: zgcd_zmult_cancel)
```
```   217
```
```   218 lemma zdvd_iff_zgcd: "0 < m ==> (m dvd n) = (zgcd (n, m) = m)"
```
```   219   apply safe
```
```   220    apply (rule_tac [2] n = "zgcd (n, m)" in zdvd_trans)
```
```   221     apply (rule_tac [3] zgcd_zdvd1, simp_all)
```
```   222   apply (unfold dvd_def, auto)
```
```   223   done
```
```   224
```
```   225
```
```   226 subsection {* Congruences *}
```
```   227
```
```   228 lemma zcong_1 [simp]: "[a = b] (mod 1)"
```
```   229   by (unfold zcong_def, auto)
```
```   230
```
```   231 lemma zcong_refl [simp]: "[k = k] (mod m)"
```
```   232   by (unfold zcong_def, auto)
```
```   233
```
```   234 lemma zcong_sym: "[a = b] (mod m) = [b = a] (mod m)"
```
```   235   apply (unfold zcong_def dvd_def, auto)
```
```   236    apply (rule_tac [!] x = "-k" in exI, auto)
```
```   237   done
```
```   238
```
```   239 lemma zcong_zadd:
```
```   240     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a + c = b + d] (mod m)"
```
```   241   apply (unfold zcong_def)
```
```   242   apply (rule_tac s = "(a - b) + (c - d)" in subst)
```
```   243    apply (rule_tac [2] zdvd_zadd, auto)
```
```   244   done
```
```   245
```
```   246 lemma zcong_zdiff:
```
```   247     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a - c = b - d] (mod m)"
```
```   248   apply (unfold zcong_def)
```
```   249   apply (rule_tac s = "(a - b) - (c - d)" in subst)
```
```   250    apply (rule_tac [2] zdvd_zdiff, auto)
```
```   251   done
```
```   252
```
```   253 lemma zcong_trans:
```
```   254     "[a = b] (mod m) ==> [b = c] (mod m) ==> [a = c] (mod m)"
```
```   255   apply (unfold zcong_def dvd_def, auto)
```
```   256   apply (rule_tac x = "k + ka" in exI)
```
```   257   apply (simp add: zadd_ac zadd_zmult_distrib2)
```
```   258   done
```
```   259
```
```   260 lemma zcong_zmult:
```
```   261     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a * c = b * d] (mod m)"
```
```   262   apply (rule_tac b = "b * c" in zcong_trans)
```
```   263    apply (unfold zcong_def)
```
```   264    apply (rule_tac s = "c * (a - b)" in subst)
```
```   265     apply (rule_tac [3] s = "b * (c - d)" in subst)
```
```   266      prefer 4
```
```   267      apply (blast intro: zdvd_zmult)
```
```   268     prefer 2
```
```   269     apply (blast intro: zdvd_zmult)
```
```   270    apply (simp_all add: zdiff_zmult_distrib2 zmult_commute)
```
```   271   done
```
```   272
```
```   273 lemma zcong_scalar: "[a = b] (mod m) ==> [a * k = b * k] (mod m)"
```
```   274   by (rule zcong_zmult, simp_all)
```
```   275
```
```   276 lemma zcong_scalar2: "[a = b] (mod m) ==> [k * a = k * b] (mod m)"
```
```   277   by (rule zcong_zmult, simp_all)
```
```   278
```
```   279 lemma zcong_zmult_self: "[a * m = b * m] (mod m)"
```
```   280   apply (unfold zcong_def)
```
```   281   apply (rule zdvd_zdiff, simp_all)
```
```   282   done
```
```   283
```
```   284 lemma zcong_square:
```
```   285    "[|p \<in> zprime;  0 < a;  [a * a = 1] (mod p)|]
```
```   286     ==> [a = 1] (mod p) \<or> [a = p - 1] (mod p)"
```
```   287   apply (unfold zcong_def)
```
```   288   apply (rule zprime_zdvd_zmult)
```
```   289     apply (rule_tac [3] s = "a * a - 1 + p * (1 - a)" in subst)
```
```   290      prefer 4
```
```   291      apply (simp add: zdvd_reduce)
```
```   292     apply (simp_all add: zdiff_zmult_distrib zmult_commute zdiff_zmult_distrib2)
```
```   293   done
```
```   294
```
```   295 lemma zcong_cancel:
```
```   296   "0 \<le> m ==>
```
```   297     zgcd (k, m) = 1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
```
```   298   apply safe
```
```   299    prefer 2
```
```   300    apply (blast intro: zcong_scalar)
```
```   301   apply (case_tac "b < a")
```
```   302    prefer 2
```
```   303    apply (subst zcong_sym)
```
```   304    apply (unfold zcong_def)
```
```   305    apply (rule_tac [!] zrelprime_zdvd_zmult)
```
```   306      apply (simp_all add: zdiff_zmult_distrib)
```
```   307   apply (subgoal_tac "m dvd (-(a * k - b * k))")
```
```   308    apply simp
```
```   309   apply (subst zdvd_zminus_iff, assumption)
```
```   310   done
```
```   311
```
```   312 lemma zcong_cancel2:
```
```   313   "0 \<le> m ==>
```
```   314     zgcd (k, m) = 1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
```
```   315   by (simp add: zmult_commute zcong_cancel)
```
```   316
```
```   317 lemma zcong_zgcd_zmult_zmod:
```
```   318   "[a = b] (mod m) ==> [a = b] (mod n) ==> zgcd (m, n) = 1
```
```   319     ==> [a = b] (mod m * n)"
```
```   320   apply (unfold zcong_def dvd_def, auto)
```
```   321   apply (subgoal_tac "m dvd n * ka")
```
```   322    apply (subgoal_tac "m dvd ka")
```
```   323     apply (case_tac [2] "0 \<le> ka")
```
```   324      prefer 3
```
```   325      apply (subst zdvd_zminus_iff [symmetric])
```
```   326      apply (rule_tac n = n in zrelprime_zdvd_zmult)
```
```   327       apply (simp add: zgcd_commute)
```
```   328      apply (simp add: zmult_commute zdvd_zminus_iff)
```
```   329     prefer 2
```
```   330     apply (rule_tac n = n in zrelprime_zdvd_zmult)
```
```   331      apply (simp add: zgcd_commute)
```
```   332     apply (simp add: zmult_commute)
```
```   333    apply (auto simp add: dvd_def)
```
```   334   done
```
```   335
```
```   336 lemma zcong_zless_imp_eq:
```
```   337   "0 \<le> a ==>
```
```   338     a < m ==> 0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
```
```   339   apply (unfold zcong_def dvd_def, auto)
```
```   340   apply (drule_tac f = "\<lambda>z. z mod m" in arg_cong)
```
```   341   apply (cut_tac x = a and y = b in linorder_less_linear, auto)
```
```   342    apply (subgoal_tac [2] "(a - b) mod m = a - b")
```
```   343     apply (rule_tac [3] mod_pos_pos_trivial, auto)
```
```   344   apply (subgoal_tac "(m + (a - b)) mod m = m + (a - b)")
```
```   345    apply (rule_tac [2] mod_pos_pos_trivial, auto)
```
```   346   done
```
```   347
```
```   348 lemma zcong_square_zless:
```
```   349   "p \<in> zprime ==> 0 < a ==> a < p ==>
```
```   350     [a * a = 1] (mod p) ==> a = 1 \<or> a = p - 1"
```
```   351   apply (cut_tac p = p and a = a in zcong_square)
```
```   352      apply (simp add: zprime_def)
```
```   353     apply (auto intro: zcong_zless_imp_eq)
```
```   354   done
```
```   355
```
```   356 lemma zcong_not:
```
```   357     "0 < a ==> a < m ==> 0 < b ==> b < a ==> \<not> [a = b] (mod m)"
```
```   358   apply (unfold zcong_def)
```
```   359   apply (rule zdvd_not_zless, auto)
```
```   360   done
```
```   361
```
```   362 lemma zcong_zless_0:
```
```   363     "0 \<le> a ==> a < m ==> [a = 0] (mod m) ==> a = 0"
```
```   364   apply (unfold zcong_def dvd_def, auto)
```
```   365   apply (subgoal_tac "0 < m")
```
```   366    apply (simp add: zero_le_mult_iff)
```
```   367    apply (subgoal_tac "m * k < m * 1")
```
```   368     apply (drule mult_less_cancel_left [THEN iffD1])
```
```   369     apply (auto simp add: linorder_neq_iff)
```
```   370   done
```
```   371
```
```   372 lemma zcong_zless_unique:
```
```   373     "0 < m ==> (\<exists>!b. 0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
```
```   374   apply auto
```
```   375    apply (subgoal_tac [2] "[b = y] (mod m)")
```
```   376     apply (case_tac [2] "b = 0")
```
```   377      apply (case_tac [3] "y = 0")
```
```   378       apply (auto intro: zcong_trans zcong_zless_0 zcong_zless_imp_eq order_less_le
```
```   379         simp add: zcong_sym)
```
```   380   apply (unfold zcong_def dvd_def)
```
```   381   apply (rule_tac x = "a mod m" in exI, auto)
```
```   382   apply (rule_tac x = "-(a div m)" in exI)
```
```   383   apply (simp add: diff_eq_eq eq_diff_eq add_commute)
```
```   384   done
```
```   385
```
```   386 lemma zcong_iff_lin: "([a = b] (mod m)) = (\<exists>k. b = a + m * k)"
```
```   387   apply (unfold zcong_def dvd_def, auto)
```
```   388    apply (rule_tac [!] x = "-k" in exI, auto)
```
```   389   done
```
```   390
```
```   391 lemma zgcd_zcong_zgcd:
```
```   392   "0 < m ==>
```
```   393     zgcd (a, m) = 1 ==> [a = b] (mod m) ==> zgcd (b, m) = 1"
```
```   394   by (auto simp add: zcong_iff_lin)
```
```   395
```
```   396 lemma zcong_zmod_aux:
```
```   397      "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
```
```   398   by(simp add: zdiff_zmult_distrib2 add_diff_eq eq_diff_eq add_ac)
```
```   399
```
```   400 lemma zcong_zmod: "[a = b] (mod m) = [a mod m = b mod m] (mod m)"
```
```   401   apply (unfold zcong_def)
```
```   402   apply (rule_tac t = "a - b" in ssubst)
```
```   403   apply (rule_tac m = m in zcong_zmod_aux)
```
```   404   apply (rule trans)
```
```   405    apply (rule_tac [2] k = m and m = "a div m - b div m" in zdvd_reduce)
```
```   406   apply (simp add: zadd_commute)
```
```   407   done
```
```   408
```
```   409 lemma zcong_zmod_eq: "0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
```
```   410   apply auto
```
```   411    apply (rule_tac m = m in zcong_zless_imp_eq)
```
```   412        prefer 5
```
```   413        apply (subst zcong_zmod [symmetric], simp_all)
```
```   414   apply (unfold zcong_def dvd_def)
```
```   415   apply (rule_tac x = "a div m - b div m" in exI)
```
```   416   apply (rule_tac m1 = m in zcong_zmod_aux [THEN trans], auto)
```
```   417   done
```
```   418
```
```   419 lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
```
```   420   by (auto simp add: zcong_def)
```
```   421
```
```   422 lemma zcong_zero [iff]: "[a = b] (mod 0) = (a = b)"
```
```   423   by (auto simp add: zcong_def)
```
```   424
```
```   425 lemma "[a = b] (mod m) = (a mod m = b mod m)"
```
```   426   apply (case_tac "m = 0", simp add: DIVISION_BY_ZERO)
```
```   427   apply (simp add: linorder_neq_iff)
```
```   428   apply (erule disjE)
```
```   429    prefer 2 apply (simp add: zcong_zmod_eq)
```
```   430   txt{*Remainding case: @{term "m<0"}*}
```
```   431   apply (rule_tac t = m in zminus_zminus [THEN subst])
```
```   432   apply (subst zcong_zminus)
```
```   433   apply (subst zcong_zmod_eq, arith)
```
```   434   apply (frule neg_mod_bound [of _ a], frule neg_mod_bound [of _ b])
```
```   435   apply (simp add: zmod_zminus2_eq_if del: neg_mod_bound)
```
```   436   done
```
```   437
```
```   438 subsection {* Modulo *}
```
```   439
```
```   440 lemma zmod_zdvd_zmod:
```
```   441     "0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
```
```   442   apply (unfold dvd_def, auto)
```
```   443   apply (subst zcong_zmod_eq [symmetric])
```
```   444    prefer 2
```
```   445    apply (subst zcong_iff_lin)
```
```   446    apply (rule_tac x = "k * (a div (m * k))" in exI)
```
```   447    apply (simp add:zmult_assoc [symmetric], assumption)
```
```   448   done
```
```   449
```
```   450
```
```   451 subsection {* Extended GCD *}
```
```   452
```
```   453 declare xzgcda.simps [simp del]
```
```   454
```
```   455 lemma xzgcd_correct_aux1:
```
```   456   "zgcd (r', r) = k --> 0 < r -->
```
```   457     (\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn))"
```
```   458   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
```
```   459     z = s and aa = t' and ab = t in xzgcda.induct)
```
```   460   apply (subst zgcd_eq)
```
```   461   apply (subst xzgcda.simps, auto)
```
```   462   apply (case_tac "r' mod r = 0")
```
```   463    prefer 2
```
```   464    apply (frule_tac a = "r'" in pos_mod_sign, auto)
```
```   465   apply (rule exI)
```
```   466   apply (rule exI)
```
```   467   apply (subst xzgcda.simps, auto)
```
```   468   apply (simp add: abs_if)
```
```   469   done
```
```   470
```
```   471 lemma xzgcd_correct_aux2:
```
```   472   "(\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn)) --> 0 < r -->
```
```   473     zgcd (r', r) = k"
```
```   474   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
```
```   475     z = s and aa = t' and ab = t in xzgcda.induct)
```
```   476   apply (subst zgcd_eq)
```
```   477   apply (subst xzgcda.simps)
```
```   478   apply (auto simp add: linorder_not_le)
```
```   479   apply (case_tac "r' mod r = 0")
```
```   480    prefer 2
```
```   481    apply (frule_tac a = "r'" in pos_mod_sign, auto)
```
```   482   apply (erule_tac P = "xzgcda ?u = ?v" in rev_mp)
```
```   483   apply (subst xzgcda.simps, auto)
```
```   484   apply (simp add: abs_if)
```
```   485   done
```
```   486
```
```   487 lemma xzgcd_correct:
```
```   488     "0 < n ==> (zgcd (m, n) = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
```
```   489   apply (unfold xzgcd_def)
```
```   490   apply (rule iffI)
```
```   491    apply (rule_tac [2] xzgcd_correct_aux2 [THEN mp, THEN mp])
```
```   492     apply (rule xzgcd_correct_aux1 [THEN mp, THEN mp], auto)
```
```   493   done
```
```   494
```
```   495
```
```   496 text {* \medskip @{term xzgcd} linear *}
```
```   497
```
```   498 lemma xzgcda_linear_aux1:
```
```   499   "(a - r * b) * m + (c - r * d) * (n::int) =
```
```   500    (a * m + c * n) - r * (b * m + d * n)"
```
```   501   by (simp add: zdiff_zmult_distrib zadd_zmult_distrib2 zmult_assoc)
```
```   502
```
```   503 lemma xzgcda_linear_aux2:
```
```   504   "r' = s' * m + t' * n ==> r = s * m + t * n
```
```   505     ==> (r' mod r) = (s' - (r' div r) * s) * m + (t' - (r' div r) * t) * (n::int)"
```
```   506   apply (rule trans)
```
```   507    apply (rule_tac [2] xzgcda_linear_aux1 [symmetric])
```
```   508   apply (simp add: eq_diff_eq mult_commute)
```
```   509   done
```
```   510
```
```   511 lemma order_le_neq_implies_less: "(x::'a::order) \<le> y ==> x \<noteq> y ==> x < y"
```
```   512   by (rule iffD2 [OF order_less_le conjI])
```
```   513
```
```   514 lemma xzgcda_linear [rule_format]:
```
```   515   "0 < r --> xzgcda (m, n, r', r, s', s, t', t) = (rn, sn, tn) -->
```
```   516     r' = s' * m + t' * n -->  r = s * m + t * n --> rn = sn * m + tn * n"
```
```   517   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
```
```   518     z = s and aa = t' and ab = t in xzgcda.induct)
```
```   519   apply (subst xzgcda.simps)
```
```   520   apply (simp (no_asm))
```
```   521   apply (rule impI)+
```
```   522   apply (case_tac "r' mod r = 0")
```
```   523    apply (simp add: xzgcda.simps, clarify)
```
```   524   apply (subgoal_tac "0 < r' mod r")
```
```   525    apply (rule_tac [2] order_le_neq_implies_less)
```
```   526    apply (rule_tac [2] pos_mod_sign)
```
```   527     apply (cut_tac m = m and n = n and r' = r' and r = r and s' = s' and
```
```   528       s = s and t' = t' and t = t in xzgcda_linear_aux2, auto)
```
```   529   done
```
```   530
```
```   531 lemma xzgcd_linear:
```
```   532     "0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
```
```   533   apply (unfold xzgcd_def)
```
```   534   apply (erule xzgcda_linear, assumption, auto)
```
```   535   done
```
```   536
```
```   537 lemma zgcd_ex_linear:
```
```   538     "0 < n ==> zgcd (m, n) = k ==> (\<exists>s t. k = s * m + t * n)"
```
```   539   apply (simp add: xzgcd_correct, safe)
```
```   540   apply (rule exI)+
```
```   541   apply (erule xzgcd_linear, auto)
```
```   542   done
```
```   543
```
```   544 lemma zcong_lineq_ex:
```
```   545     "0 < n ==> zgcd (a, n) = 1 ==> \<exists>x. [a * x = 1] (mod n)"
```
```   546   apply (cut_tac m = a and n = n and k = 1 in zgcd_ex_linear, safe)
```
```   547   apply (rule_tac x = s in exI)
```
```   548   apply (rule_tac b = "s * a + t * n" in zcong_trans)
```
```   549    prefer 2
```
```   550    apply simp
```
```   551   apply (unfold zcong_def)
```
```   552   apply (simp (no_asm) add: zmult_commute zdvd_zminus_iff)
```
```   553   done
```
```   554
```
```   555 lemma zcong_lineq_unique:
```
```   556   "0 < n ==>
```
```   557     zgcd (a, n) = 1 ==> \<exists>!x. 0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
```
```   558   apply auto
```
```   559    apply (rule_tac [2] zcong_zless_imp_eq)
```
```   560        apply (tactic {* stac (thm "zcong_cancel2" RS sym) 6 *})
```
```   561          apply (rule_tac [8] zcong_trans)
```
```   562           apply (simp_all (no_asm_simp))
```
```   563    prefer 2
```
```   564    apply (simp add: zcong_sym)
```
```   565   apply (cut_tac a = a and n = n in zcong_lineq_ex, auto)
```
```   566   apply (rule_tac x = "x * b mod n" in exI, safe)
```
```   567     apply (simp_all (no_asm_simp))
```
```   568   apply (subst zcong_zmod)
```
```   569   apply (subst zmod_zmult1_eq [symmetric])
```
```   570   apply (subst zcong_zmod [symmetric])
```
```   571   apply (subgoal_tac "[a * x * b = 1 * b] (mod n)")
```
```   572    apply (rule_tac [2] zcong_zmult)
```
```   573     apply (simp_all add: zmult_assoc)
```
```   574   done
```
```   575
```
```   576 end
```