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