src/HOL/NumberTheory/IntPrimes.thy
author wenzelm
Fri Mar 28 19:43:54 2008 +0100 (2008-03-28)
changeset 26462 dac4e2bce00d
parent 25596 ad9e3594f3f3
child 27368 9f90ac19e32b
permissions -rw-r--r--
avoid rebinding of existing facts;
     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
    10 imports Primes
    11 begin
    12 
    13 text {*
    14   The @{text dvd} relation, GCD, Euclid's extended algorithm, primes,
    15   congruences (all on the Integers).  Comparable to theory @{text
    16   Primes}, but @{text dvd} is included here as it is not present in
    17   main HOL.  Also includes extended GCD and congruences not present in
    18   @{text Primes}.
    19 *}
    20 
    21 
    22 subsection {* Definitions *}
    23 
    24 consts
    25   xzgcda :: "int * int * int * int * int * int * int * int => int * int * int"
    26 
    27 recdef xzgcda
    28   "measure ((\<lambda>(m, n, r', r, s', s, t', t). nat r)
    29     :: int * int * int * int *int * int * int * int => nat)"
    30   "xzgcda (m, n, r', r, s', s, t', t) =
    31 	(if r \<le> 0 then (r', s', t')
    32 	 else xzgcda (m, n, r, r' mod r, 
    33 		      s, s' - (r' div r) * s, 
    34 		      t, t' - (r' div r) * t))"
    35 
    36 definition
    37   zgcd :: "int * int => int" where
    38   "zgcd = (\<lambda>(x,y). int (gcd (nat (abs x), nat (abs y))))"
    39 
    40 definition
    41   zprime :: "int \<Rightarrow> bool" where
    42   "zprime p = (1 < p \<and> (\<forall>m. 0 <= m & m dvd p --> m = 1 \<or> m = p))"
    43 
    44 definition
    45   xzgcd :: "int => int => int * int * int" where
    46   "xzgcd m n = xzgcda (m, n, m, n, 1, 0, 0, 1)"
    47 
    48 definition
    49   zcong :: "int => int => int => bool"  ("(1[_ = _] '(mod _'))") where
    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   by (metis abs_of_nonneg zdvd_triv_right zgcd_greatest_iff zgcd_zmult_distrib2_abs zmult_1_right)
   146 
   147 lemma zrelprime_zdvd_zmult: "zgcd (n, k) = 1 ==> k dvd m * n ==> k dvd m"
   148   apply (case_tac "0 \<le> m")
   149    apply (blast intro: zrelprime_zdvd_zmult_aux)
   150   apply (subgoal_tac "k dvd -m")
   151    apply (rule_tac [2] zrelprime_zdvd_zmult_aux, auto)
   152   done
   153 
   154 lemma zgcd_geq_zero: "0 <= zgcd(x,y)"
   155   by (auto simp add: zgcd_def)
   156 
   157 text{*This is merely a sanity check on zprime, since the previous version
   158       denoted the empty set.*}
   159 lemma "zprime 2"
   160   apply (auto simp add: zprime_def) 
   161   apply (frule zdvd_imp_le, simp) 
   162   apply (auto simp add: order_le_less dvd_def) 
   163   done
   164 
   165 lemma zprime_imp_zrelprime:
   166     "zprime p ==> \<not> p dvd n ==> zgcd (n, p) = 1"
   167   apply (auto simp add: zprime_def)
   168   apply (metis zgcd_commute zgcd_geq_zero zgcd_zdvd1 zgcd_zdvd2)
   169   done
   170 
   171 lemma zless_zprime_imp_zrelprime:
   172     "zprime p ==> 0 < n ==> n < p ==> zgcd (n, p) = 1"
   173   apply (erule zprime_imp_zrelprime)
   174   apply (erule zdvd_not_zless, assumption)
   175   done
   176 
   177 lemma zprime_zdvd_zmult:
   178     "0 \<le> (m::int) ==> zprime p ==> p dvd m * n ==> p dvd m \<or> p dvd n"
   179   by (metis igcd_dvd1 igcd_dvd2 igcd_pos zprime_def zrelprime_dvd_mult)
   180 
   181 lemma zgcd_zadd_zmult [simp]: "zgcd (m + n * k, n) = zgcd (m, n)"
   182   apply (rule zgcd_eq [THEN trans])
   183   apply (simp add: zmod_zadd1_eq)
   184   apply (rule zgcd_eq [symmetric])
   185   done
   186 
   187 lemma zgcd_zdvd_zgcd_zmult: "zgcd (m, n) dvd zgcd (k * m, n)"
   188   apply (simp add: zgcd_greatest_iff)
   189   apply (blast intro: zdvd_trans)
   190   done
   191 
   192 lemma zgcd_zmult_zdvd_zgcd:
   193     "zgcd (k, n) = 1 ==> zgcd (k * m, n) dvd zgcd (m, n)"
   194   apply (simp add: zgcd_greatest_iff)
   195   apply (rule_tac n = k in zrelprime_zdvd_zmult)
   196    prefer 2
   197    apply (simp add: zmult_commute)
   198   apply (metis zgcd_1 zgcd_commute zgcd_left_commute)
   199   done
   200 
   201 lemma zgcd_zmult_cancel: "zgcd (k, n) = 1 ==> zgcd (k * m, n) = zgcd (m, n)"
   202   by (simp add: zgcd_def nat_abs_mult_distrib gcd_mult_cancel)
   203 
   204 lemma zgcd_zgcd_zmult:
   205     "zgcd (k, m) = 1 ==> zgcd (n, m) = 1 ==> zgcd (k * n, m) = 1"
   206   by (simp add: zgcd_zmult_cancel)
   207 
   208 lemma zdvd_iff_zgcd: "0 < m ==> (m dvd n) = (zgcd (n, m) = m)"
   209   by (metis abs_of_pos zdvd_mult_div_cancel zgcd_0 zgcd_commute zgcd_geq_zero zgcd_zdvd2 zgcd_zmult_eq_self)
   210 
   211 
   212 
   213 subsection {* Congruences *}
   214 
   215 lemma zcong_1 [simp]: "[a = b] (mod 1)"
   216   by (unfold zcong_def, auto)
   217 
   218 lemma zcong_refl [simp]: "[k = k] (mod m)"
   219   by (unfold zcong_def, auto)
   220 
   221 lemma zcong_sym: "[a = b] (mod m) = [b = a] (mod m)"
   222   apply (unfold zcong_def dvd_def, auto)
   223    apply (rule_tac [!] x = "-k" in exI, auto)
   224   done
   225 
   226 lemma zcong_zadd:
   227     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a + c = b + d] (mod m)"
   228   apply (unfold zcong_def)
   229   apply (rule_tac s = "(a - b) + (c - d)" in subst)
   230    apply (rule_tac [2] zdvd_zadd, auto)
   231   done
   232 
   233 lemma zcong_zdiff:
   234     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a - c = b - d] (mod m)"
   235   apply (unfold zcong_def)
   236   apply (rule_tac s = "(a - b) - (c - d)" in subst)
   237    apply (rule_tac [2] zdvd_zdiff, auto)
   238   done
   239 
   240 lemma zcong_trans:
   241     "[a = b] (mod m) ==> [b = c] (mod m) ==> [a = c] (mod m)"
   242   apply (unfold zcong_def dvd_def, auto)
   243   apply (rule_tac x = "k + ka" in exI)
   244   apply (simp add: zadd_ac zadd_zmult_distrib2)
   245   done
   246 
   247 lemma zcong_zmult:
   248     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a * c = b * d] (mod m)"
   249   apply (rule_tac b = "b * c" in zcong_trans)
   250    apply (unfold zcong_def)
   251   apply (metis zdiff_zmult_distrib2 zdvd_zmult zmult_commute)
   252   apply (metis zdiff_zmult_distrib2 zdvd_zmult)
   253   done
   254 
   255 lemma zcong_scalar: "[a = b] (mod m) ==> [a * k = b * k] (mod m)"
   256   by (rule zcong_zmult, simp_all)
   257 
   258 lemma zcong_scalar2: "[a = b] (mod m) ==> [k * a = k * b] (mod m)"
   259   by (rule zcong_zmult, simp_all)
   260 
   261 lemma zcong_zmult_self: "[a * m = b * m] (mod m)"
   262   apply (unfold zcong_def)
   263   apply (rule zdvd_zdiff, simp_all)
   264   done
   265 
   266 lemma zcong_square:
   267    "[| zprime p;  0 < a;  [a * a = 1] (mod p)|]
   268     ==> [a = 1] (mod p) \<or> [a = p - 1] (mod p)"
   269   apply (unfold zcong_def)
   270   apply (rule zprime_zdvd_zmult)
   271     apply (rule_tac [3] s = "a * a - 1 + p * (1 - a)" in subst)
   272      prefer 4
   273      apply (simp add: zdvd_reduce)
   274     apply (simp_all add: zdiff_zmult_distrib zmult_commute zdiff_zmult_distrib2)
   275   done
   276 
   277 lemma zcong_cancel:
   278   "0 \<le> m ==>
   279     zgcd (k, m) = 1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
   280   apply safe
   281    prefer 2
   282    apply (blast intro: zcong_scalar)
   283   apply (case_tac "b < a")
   284    prefer 2
   285    apply (subst zcong_sym)
   286    apply (unfold zcong_def)
   287    apply (rule_tac [!] zrelprime_zdvd_zmult)
   288      apply (simp_all add: zdiff_zmult_distrib)
   289   apply (subgoal_tac "m dvd (-(a * k - b * k))")
   290    apply simp
   291   apply (subst zdvd_zminus_iff, assumption)
   292   done
   293 
   294 lemma zcong_cancel2:
   295   "0 \<le> m ==>
   296     zgcd (k, m) = 1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
   297   by (simp add: zmult_commute zcong_cancel)
   298 
   299 lemma zcong_zgcd_zmult_zmod:
   300   "[a = b] (mod m) ==> [a = b] (mod n) ==> zgcd (m, n) = 1
   301     ==> [a = b] (mod m * n)"
   302   apply (unfold zcong_def dvd_def, auto)
   303   apply (subgoal_tac "m dvd n * ka")
   304    apply (subgoal_tac "m dvd ka")
   305     apply (case_tac [2] "0 \<le> ka")
   306   apply (metis zdvd_mult_div_cancel zdvd_refl zdvd_zminus2_iff zdvd_zmultD2 zgcd_zminus zmult_commute zmult_zminus zrelprime_zdvd_zmult)
   307   apply (metis IntDiv.zdvd_abs1 abs_of_nonneg zadd_0 zgcd_0_left zgcd_commute zgcd_zadd_zmult zgcd_zdvd_zgcd_zmult zgcd_zmult_distrib2_abs zmult_1_right zmult_commute)
   308   apply (metis abs_eq_0 int_0_neq_1 mult_le_0_iff  zdvd_mono zdvd_mult_cancel zdvd_mult_cancel1 zdvd_refl zdvd_triv_left zdvd_zmult2 zero_le_mult_iff zgcd_greatest_iff zle_anti_sym zle_linear zle_refl zmult_commute zrelprime_zdvd_zmult)
   309   apply (metis zdvd_triv_left)
   310   done
   311 
   312 lemma zcong_zless_imp_eq:
   313   "0 \<le> a ==>
   314     a < m ==> 0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
   315   apply (unfold zcong_def dvd_def, auto)
   316   apply (drule_tac f = "\<lambda>z. z mod m" in arg_cong)
   317   apply (metis diff_add_cancel mod_pos_pos_trivial zadd_0 zadd_commute zmod_eq_0_iff zmod_zadd_right_eq)
   318   done
   319 
   320 lemma zcong_square_zless:
   321   "zprime p ==> 0 < a ==> a < p ==>
   322     [a * a = 1] (mod p) ==> a = 1 \<or> a = p - 1"
   323   apply (cut_tac p = p and a = a in zcong_square)
   324      apply (simp add: zprime_def)
   325     apply (auto intro: zcong_zless_imp_eq)
   326   done
   327 
   328 lemma zcong_not:
   329     "0 < a ==> a < m ==> 0 < b ==> b < a ==> \<not> [a = b] (mod m)"
   330   apply (unfold zcong_def)
   331   apply (rule zdvd_not_zless, auto)
   332   done
   333 
   334 lemma zcong_zless_0:
   335     "0 \<le> a ==> a < m ==> [a = 0] (mod m) ==> a = 0"
   336   apply (unfold zcong_def dvd_def, auto)
   337   apply (metis div_pos_pos_trivial linorder_not_less zdiv_zmult_self2 zle_refl zle_trans)
   338   done
   339 
   340 lemma zcong_zless_unique:
   341     "0 < m ==> (\<exists>!b. 0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
   342   apply auto
   343    prefer 2 apply (metis zcong_sym zcong_trans zcong_zless_imp_eq)
   344   apply (unfold zcong_def dvd_def)
   345   apply (rule_tac x = "a mod m" in exI, auto)
   346   apply (metis zmult_div_cancel)
   347   done
   348 
   349 lemma zcong_iff_lin: "([a = b] (mod m)) = (\<exists>k. b = a + m * k)"
   350   apply (unfold zcong_def dvd_def, auto)
   351    apply (rule_tac [!] x = "-k" in exI, auto)
   352   done
   353 
   354 lemma zgcd_zcong_zgcd:
   355   "0 < m ==>
   356     zgcd (a, m) = 1 ==> [a = b] (mod m) ==> zgcd (b, m) = 1"
   357   by (auto simp add: zcong_iff_lin)
   358 
   359 lemma zcong_zmod_aux:
   360      "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
   361   by(simp add: zdiff_zmult_distrib2 add_diff_eq eq_diff_eq add_ac)
   362 
   363 lemma zcong_zmod: "[a = b] (mod m) = [a mod m = b mod m] (mod m)"
   364   apply (unfold zcong_def)
   365   apply (rule_tac t = "a - b" in ssubst)
   366   apply (rule_tac m = m in zcong_zmod_aux)
   367   apply (rule trans)
   368    apply (rule_tac [2] k = m and m = "a div m - b div m" in zdvd_reduce)
   369   apply (simp add: zadd_commute)
   370   done
   371 
   372 lemma zcong_zmod_eq: "0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
   373   apply auto
   374   apply (metis pos_mod_conj zcong_zless_imp_eq zcong_zmod)
   375   apply (metis zcong_refl zcong_zmod)
   376   done
   377 
   378 lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
   379   by (auto simp add: zcong_def)
   380 
   381 lemma zcong_zero [iff]: "[a = b] (mod 0) = (a = b)"
   382   by (auto simp add: zcong_def)
   383 
   384 lemma "[a = b] (mod m) = (a mod m = b mod m)"
   385   apply (case_tac "m = 0", simp add: DIVISION_BY_ZERO)
   386   apply (simp add: linorder_neq_iff)
   387   apply (erule disjE)  
   388    prefer 2 apply (simp add: zcong_zmod_eq)
   389   txt{*Remainding case: @{term "m<0"}*}
   390   apply (rule_tac t = m in zminus_zminus [THEN subst])
   391   apply (subst zcong_zminus)
   392   apply (subst zcong_zmod_eq, arith)
   393   apply (frule neg_mod_bound [of _ a], frule neg_mod_bound [of _ b]) 
   394   apply (simp add: zmod_zminus2_eq_if del: neg_mod_bound)
   395   done
   396 
   397 subsection {* Modulo *}
   398 
   399 lemma zmod_zdvd_zmod:
   400     "0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
   401   apply (unfold dvd_def, auto)
   402   apply (subst zcong_zmod_eq [symmetric])
   403    prefer 2
   404    apply (subst zcong_iff_lin)
   405    apply (rule_tac x = "k * (a div (m * k))" in exI)
   406    apply (simp add:zmult_assoc [symmetric], assumption)
   407   done
   408 
   409 
   410 subsection {* Extended GCD *}
   411 
   412 declare xzgcda.simps [simp del]
   413 
   414 lemma xzgcd_correct_aux1:
   415   "zgcd (r', r) = k --> 0 < r -->
   416     (\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn))"
   417   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
   418     z = s and aa = t' and ab = t in xzgcda.induct)
   419   apply (subst zgcd_eq)
   420   apply (subst xzgcda.simps, auto)
   421   apply (case_tac "r' mod r = 0")
   422    prefer 2
   423    apply (frule_tac a = "r'" in pos_mod_sign, auto)
   424   apply (rule exI)
   425   apply (rule exI)
   426   apply (subst xzgcda.simps, auto)
   427   done
   428 
   429 lemma xzgcd_correct_aux2:
   430   "(\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn)) --> 0 < r -->
   431     zgcd (r', r) = k"
   432   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
   433     z = s and aa = t' and ab = t in xzgcda.induct)
   434   apply (subst zgcd_eq)
   435   apply (subst xzgcda.simps)
   436   apply (auto simp add: linorder_not_le)
   437   apply (case_tac "r' mod r = 0")
   438    prefer 2
   439    apply (frule_tac a = "r'" in pos_mod_sign, auto)
   440   apply (metis Pair_eq simps zle_refl)
   441   done
   442 
   443 lemma xzgcd_correct:
   444     "0 < n ==> (zgcd (m, n) = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
   445   apply (unfold xzgcd_def)
   446   apply (rule iffI)
   447    apply (rule_tac [2] xzgcd_correct_aux2 [THEN mp, THEN mp])
   448     apply (rule xzgcd_correct_aux1 [THEN mp, THEN mp], auto)
   449   done
   450 
   451 
   452 text {* \medskip @{term xzgcd} linear *}
   453 
   454 lemma xzgcda_linear_aux1:
   455   "(a - r * b) * m + (c - r * d) * (n::int) =
   456    (a * m + c * n) - r * (b * m + d * n)"
   457   by (simp add: zdiff_zmult_distrib zadd_zmult_distrib2 zmult_assoc)
   458 
   459 lemma xzgcda_linear_aux2:
   460   "r' = s' * m + t' * n ==> r = s * m + t * n
   461     ==> (r' mod r) = (s' - (r' div r) * s) * m + (t' - (r' div r) * t) * (n::int)"
   462   apply (rule trans)
   463    apply (rule_tac [2] xzgcda_linear_aux1 [symmetric])
   464   apply (simp add: eq_diff_eq mult_commute)
   465   done
   466 
   467 lemma order_le_neq_implies_less: "(x::'a::order) \<le> y ==> x \<noteq> y ==> x < y"
   468   by (rule iffD2 [OF order_less_le conjI])
   469 
   470 lemma xzgcda_linear [rule_format]:
   471   "0 < r --> xzgcda (m, n, r', r, s', s, t', t) = (rn, sn, tn) -->
   472     r' = s' * m + t' * n -->  r = s * m + t * n --> rn = sn * m + tn * n"
   473   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
   474     z = s and aa = t' and ab = t in xzgcda.induct)
   475   apply (subst xzgcda.simps)
   476   apply (simp (no_asm))
   477   apply (rule impI)+
   478   apply (case_tac "r' mod r = 0")
   479    apply (simp add: xzgcda.simps, clarify)
   480   apply (subgoal_tac "0 < r' mod r")
   481    apply (rule_tac [2] order_le_neq_implies_less)
   482    apply (rule_tac [2] pos_mod_sign)
   483     apply (cut_tac m = m and n = n and r' = r' and r = r and s' = s' and
   484       s = s and t' = t' and t = t in xzgcda_linear_aux2, auto)
   485   done
   486 
   487 lemma xzgcd_linear:
   488     "0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
   489   apply (unfold xzgcd_def)
   490   apply (erule xzgcda_linear, assumption, auto)
   491   done
   492 
   493 lemma zgcd_ex_linear:
   494     "0 < n ==> zgcd (m, n) = k ==> (\<exists>s t. k = s * m + t * n)"
   495   apply (simp add: xzgcd_correct, safe)
   496   apply (rule exI)+
   497   apply (erule xzgcd_linear, auto)
   498   done
   499 
   500 lemma zcong_lineq_ex:
   501     "0 < n ==> zgcd (a, n) = 1 ==> \<exists>x. [a * x = 1] (mod n)"
   502   apply (cut_tac m = a and n = n and k = 1 in zgcd_ex_linear, safe)
   503   apply (rule_tac x = s in exI)
   504   apply (rule_tac b = "s * a + t * n" in zcong_trans)
   505    prefer 2
   506    apply simp
   507   apply (unfold zcong_def)
   508   apply (simp (no_asm) add: zmult_commute zdvd_zminus_iff)
   509   done
   510 
   511 lemma zcong_lineq_unique:
   512   "0 < n ==>
   513     zgcd (a, n) = 1 ==> \<exists>!x. 0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
   514   apply auto
   515    apply (rule_tac [2] zcong_zless_imp_eq)
   516        apply (tactic {* stac (thm "zcong_cancel2" RS sym) 6 *})
   517          apply (rule_tac [8] zcong_trans)
   518           apply (simp_all (no_asm_simp))
   519    prefer 2
   520    apply (simp add: zcong_sym)
   521   apply (cut_tac a = a and n = n in zcong_lineq_ex, auto)
   522   apply (rule_tac x = "x * b mod n" in exI, safe)
   523     apply (simp_all (no_asm_simp))
   524   apply (metis zcong_scalar zcong_zmod zmod_zmult1_eq zmult_1 zmult_assoc)
   525   done
   526 
   527 end