src/HOL/NumberTheory/IntPrimes.thy
author nipkow
Thu May 30 10:12:52 2002 +0200 (2002-05-30)
changeset 13187 e5434b822a96
parent 13183 c7290200b3f4
child 13193 d5234c261813
permissions -rw-r--r--
Modifications due to enhanced linear arithmetic.
     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 = Primes:
    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   xzgcd :: "int => int => int * int * int"
    25   zprime :: "int set"
    26   zcong :: "int => int => int => bool"    ("(1[_ = _] '(mod _'))")
    27 
    28 recdef xzgcda
    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)
    35 
    36 constdefs
    37   zgcd :: "int * int => int"
    38   "zgcd == \<lambda>(x,y). int (gcd (nat (abs x), nat (abs y)))"
    39 
    40 defs
    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)"
    44 
    45 
    46 lemma zabs_eq_iff:
    47     "(abs (z::int) = w) = (z = w \<and> 0 <= z \<or> z = -w \<and> z < 0)"
    48   apply (auto simp add: zabs_def)
    49   done
    50 
    51 
    52 text {* \medskip @{term gcd} lemmas *}
    53 
    54 lemma gcd_add1_eq: "gcd (m + k, k) = gcd (m + k, m)"
    55   apply (simp add: gcd_commute)
    56   done
    57 
    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)
    61   apply simp
    62   done
    63 
    64 
    65 subsection {* Divides relation *}
    66 
    67 lemma zdvd_0_right [iff]: "(m::int) dvd 0"
    68   apply (unfold dvd_def)
    69   apply (blast intro: zmult_0_right [symmetric])
    70   done
    71 
    72 lemma zdvd_0_left [iff]: "(0 dvd (m::int)) = (m = 0)"
    73   apply (unfold dvd_def)
    74   apply auto
    75   done
    76 
    77 lemma zdvd_1_left [iff]: "1 dvd (m::int)"
    78   apply (unfold dvd_def)
    79   apply simp
    80   done
    81 
    82 lemma zdvd_refl [simp]: "m dvd (m::int)"
    83   apply (unfold dvd_def)
    84   apply (blast intro: zmult_1_right [symmetric])
    85   done
    86 
    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)
    90   done
    91 
    92 lemma zdvd_zminus_iff: "(m dvd -n) = (m dvd (n::int))"
    93   apply (unfold dvd_def)
    94   apply auto
    95    apply (rule_tac [!] x = "-k" in exI)
    96   apply auto
    97   done
    98 
    99 lemma zdvd_zminus2_iff: "(-m dvd n) = (m dvd (n::int))"
   100   apply (unfold dvd_def)
   101   apply auto
   102    apply (rule_tac [!] x = "-k" in exI)
   103   apply auto
   104   done
   105 
   106 lemma zdvd_anti_sym:
   107     "0 < m ==> 0 < n ==> m dvd n ==> n dvd m ==> m = (n::int)"
   108   apply (unfold dvd_def)
   109   apply auto
   110   apply (simp add: zmult_assoc zmult_eq_self_iff int_0_less_mult_iff zmult_eq_1_iff)
   111   done
   112 
   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])
   116   done
   117 
   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])
   121   done
   122 
   123 lemma zdvd_zdiffD: "k dvd m - n ==> k dvd n ==> k dvd (m::int)"
   124   apply (subgoal_tac "m = n + (m - n)")
   125    apply (erule ssubst)
   126    apply (blast intro: zdvd_zadd)
   127   apply simp
   128   done
   129 
   130 lemma zdvd_zmult: "k dvd (n::int) ==> k dvd m * n"
   131   apply (unfold dvd_def)
   132   apply (blast intro: zmult_left_commute)
   133   done
   134 
   135 lemma zdvd_zmult2: "k dvd (m::int) ==> k dvd m * n"
   136   apply (subst zmult_commute)
   137   apply (erule zdvd_zmult)
   138   done
   139 
   140 lemma [iff]: "(k::int) dvd m * k"
   141   apply (rule zdvd_zmult)
   142   apply (rule zdvd_refl)
   143   done
   144 
   145 lemma [iff]: "(k::int) dvd k * m"
   146   apply (rule zdvd_zmult2)
   147   apply (rule zdvd_refl)
   148   done
   149 
   150 lemma zdvd_zmultD2: "j * k dvd n ==> j dvd (n::int)"
   151   apply (unfold dvd_def)
   152   apply (simp add: zmult_assoc)
   153   apply blast
   154   done
   155 
   156 lemma zdvd_zmultD: "j * k dvd n ==> k dvd (n::int)"
   157   apply (rule zdvd_zmultD2)
   158   apply (subst zmult_commute)
   159   apply assumption
   160   done
   161 
   162 lemma zdvd_zmult_mono: "i dvd m ==> j dvd (n::int) ==> i * j dvd m * n"
   163   apply (unfold dvd_def)
   164   apply clarify
   165   apply (rule_tac x = "k * ka" in exI)
   166   apply (simp add: zmult_ac)
   167   done
   168 
   169 lemma zdvd_reduce: "(k dvd n + k * m) = (k dvd (n::int))"
   170   apply (rule iffI)
   171    apply (erule_tac [2] zdvd_zadd)
   172    apply (subgoal_tac "n = (n + k * m) - k * m")
   173     apply (erule ssubst)
   174     apply (erule zdvd_zdiff)
   175     apply simp_all
   176   done
   177 
   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)
   181   done
   182 
   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 add: zdvd_zadd zdvd_zmult2)
   187   done
   188 
   189 lemma zdvd_iff_zmod_eq_0: "(k dvd n) = (n mod (k::int) = 0)"
   190   apply (unfold dvd_def)
   191   apply auto
   192   done
   193 
   194 lemma zdvd_not_zless: "0 < m ==> m < n ==> \<not> n dvd (m::int)"
   195   apply (unfold dvd_def)
   196   apply auto
   197   apply (subgoal_tac "0 < n")
   198    prefer 2
   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])
   203    apply auto
   204   done
   205 
   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])
   211   done
   212 
   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)
   222   done
   223 
   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)
   230   done
   231 
   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)
   235    apply auto
   236   done
   237 
   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)
   242    apply auto
   243   done
   244 
   245 
   246 subsection {* Euclid's Algorithm and GCD *}
   247 
   248 lemma zgcd_0 [simp]: "zgcd (m, 0) = abs m"
   249   apply (simp add: zgcd_def zabs_def)
   250   done
   251 
   252 lemma zgcd_0_left [simp]: "zgcd (0, m) = abs m"
   253   apply (simp add: zgcd_def zabs_def)
   254   done
   255 
   256 lemma zgcd_zminus [simp]: "zgcd (-m, n) = zgcd (m, n)"
   257   apply (simp add: zgcd_def)
   258   done
   259 
   260 lemma zgcd_zminus2 [simp]: "zgcd (m, -n) = zgcd (m, n)"
   261   apply (simp add: zgcd_def)
   262   done
   263 
   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])
   271   done
   272 
   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)
   277    apply auto
   278   done
   279 
   280 lemma zgcd_1 [simp]: "zgcd (m, 1) = 1"
   281   apply (simp add: zgcd_def zabs_def)
   282   done
   283 
   284 lemma zgcd_0_1_iff [simp]: "(zgcd (0, m) = 1) = (abs m = 1)"
   285   apply (simp add: zgcd_def zabs_def)
   286   done
   287 
   288 lemma zgcd_zdvd1 [iff]: "zgcd (m, n) dvd m"
   289   apply (simp add: zgcd_def zabs_def int_dvd_iff)
   290   done
   291 
   292 lemma zgcd_zdvd2 [iff]: "zgcd (m, n) dvd n"
   293   apply (simp add: zgcd_def zabs_def int_dvd_iff)
   294   done
   295 
   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)
   298   done
   299 
   300 lemma zgcd_commute: "zgcd (m, n) = zgcd (n, m)"
   301   apply (simp add: zgcd_def gcd_commute)
   302   done
   303 
   304 lemma zgcd_1_left [simp]: "zgcd (1, m) = 1"
   305   apply (simp add: zgcd_def gcd_1_left)
   306   done
   307 
   308 lemma zgcd_assoc: "zgcd (zgcd (k, m), n) = zgcd (k, zgcd (m, n))"
   309   apply (simp add: zgcd_def gcd_assoc)
   310   done
   311 
   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])
   316   done
   317 
   318 lemmas zgcd_ac = zgcd_assoc zgcd_commute zgcd_left_commute
   319   -- {* addition is an AC-operator *}
   320 
   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])
   325   done
   326 
   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)
   329   done
   330 
   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)
   333    apply simp_all
   334   done
   335 
   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)
   338    apply simp_all
   339   done
   340 
   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)
   343    apply simp_all
   344   done
   345 
   346 lemma 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)
   350   done
   351 
   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: aux)
   355   apply (subgoal_tac "k dvd -m")
   356    apply (rule_tac [2] aux)
   357      apply auto
   358   done
   359 
   360 lemma zprime_imp_zrelprime:
   361     "p \<in> zprime ==> \<not> p dvd n ==> zgcd (n, p) = 1"
   362   apply (unfold zprime_def)
   363   apply auto
   364   done
   365 
   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)
   370   apply assumption
   371   done
   372 
   373 lemma zprime_zdvd_zmult:
   374     "0 \<le> (m::int) ==> p \<in> zprime ==> p dvd m * n ==> p dvd m \<or> p dvd n"
   375   apply safe
   376   apply (rule zrelprime_zdvd_zmult)
   377    apply (rule zprime_imp_zrelprime)
   378     apply auto
   379   done
   380 
   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])
   385   done
   386 
   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)
   390   done
   391 
   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)
   396    prefer 2
   397    apply (simp add: zmult_commute)
   398   apply (subgoal_tac "zgcd (k, zgcd (k * m, n)) = zgcd (k * m, zgcd (k, n))")
   399    apply simp
   400   apply (simp (no_asm) add: zgcd_ac)
   401   done
   402 
   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)
   405   done
   406 
   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)
   410   done
   411 
   412 lemma zdvd_iff_zgcd: "0 < m ==> (m dvd n) = (zgcd (n, m) = m)"
   413   apply safe
   414    apply (rule_tac [2] n = "zgcd (n, m)" in zdvd_trans)
   415     apply (rule_tac [3] zgcd_zdvd1)
   416    apply simp_all
   417   apply (unfold dvd_def)
   418   apply auto
   419   done
   420 
   421 
   422 subsection {* Congruences *}
   423 
   424 lemma zcong_1 [simp]: "[a = b] (mod 1)"
   425   apply (unfold zcong_def)
   426   apply auto
   427   done
   428 
   429 lemma zcong_refl [simp]: "[k = k] (mod m)"
   430   apply (unfold zcong_def)
   431   apply auto
   432   done
   433 
   434 lemma zcong_sym: "[a = b] (mod m) = [b = a] (mod m)"
   435   apply (unfold zcong_def dvd_def)
   436   apply auto
   437    apply (rule_tac [!] x = "-k" in exI)
   438    apply auto
   439   done
   440 
   441 lemma zcong_zadd:
   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)
   446     apply auto
   447   done
   448 
   449 lemma zcong_zdiff:
   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)
   454     apply auto
   455   done
   456 
   457 lemma zcong_trans:
   458     "[a = b] (mod m) ==> [b = c] (mod m) ==> [a = c] (mod m)"
   459   apply (unfold zcong_def dvd_def)
   460   apply auto
   461   apply (rule_tac x = "k + ka" in exI)
   462   apply (simp add: zadd_ac zadd_zmult_distrib2)
   463   done
   464 
   465 lemma zcong_zmult:
   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)
   471      prefer 4
   472      apply (blast intro: zdvd_zmult)
   473     prefer 2
   474     apply (blast intro: zdvd_zmult)
   475    apply (simp_all add: zdiff_zmult_distrib2 zmult_commute)
   476   done
   477 
   478 lemma zcong_scalar: "[a = b] (mod m) ==> [a * k = b * k] (mod m)"
   479   apply (rule zcong_zmult)
   480   apply simp_all
   481   done
   482 
   483 lemma zcong_scalar2: "[a = b] (mod m) ==> [k * a = k * b] (mod m)"
   484   apply (rule zcong_zmult)
   485   apply simp_all
   486   done
   487 
   488 lemma zcong_zmult_self: "[a * m = b * m] (mod m)"
   489   apply (unfold zcong_def)
   490   apply (rule zdvd_zdiff)
   491    apply simp_all
   492   done
   493 
   494 lemma zcong_square:
   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)
   500      prefer 4
   501      apply (simp add: zdvd_reduce)
   502     apply (simp_all add: zdiff_zmult_distrib zmult_commute zdiff_zmult_distrib2)
   503   done
   504 
   505 lemma zcong_cancel:
   506   "0 \<le> m ==>
   507     zgcd (k, m) = 1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
   508   apply safe
   509    prefer 2
   510    apply (blast intro: zcong_scalar)
   511   apply (case_tac "b < a")
   512    prefer 2
   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)
   520   apply assumption
   521   done
   522 
   523 lemma zcong_cancel2:
   524   "0 \<le> m ==>
   525     zgcd (k, m) = 1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
   526   apply (simp add: zmult_commute zcong_cancel)
   527   done
   528 
   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)
   533   apply auto
   534   apply (subgoal_tac "m dvd n * ka")
   535    apply (subgoal_tac "m dvd ka")
   536     apply (case_tac [2] "0 \<le> ka")
   537      prefer 3
   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)
   542     prefer 2
   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)
   548   done
   549 
   550 lemma zcong_zless_imp_eq:
   551   "0 \<le> a ==>
   552     a < m ==> 0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
   553   apply (unfold zcong_def dvd_def)
   554   apply auto
   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)
   557   apply auto
   558    apply (subgoal_tac [2] "(a - b) mod m = a - b")
   559     apply (rule_tac [3] mod_pos_pos_trivial)
   560      apply auto
   561   apply (subgoal_tac "(m + (a - b)) mod m = m + (a - b)")
   562    apply (rule_tac [2] mod_pos_pos_trivial)
   563     apply auto
   564   done
   565 
   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)
   572   done
   573 
   574 lemma zcong_not:
   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)
   578    apply auto
   579   done
   580 
   581 lemma zcong_zless_0:
   582     "0 \<le> a ==> a < m ==> [a = 0] (mod m) ==> a = 0"
   583   apply (unfold zcong_def dvd_def)
   584   apply auto
   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)
   591   done
   592 
   593 lemma zcong_zless_unique:
   594     "0 < m ==> (\<exists>!b. 0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
   595   apply auto
   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
   600         simp add: zcong_sym)
   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 (cut_tac a = a and b = m in zmod_zdiv_equality)
   606   apply auto
   607   done
   608 
   609 lemma zcong_iff_lin: "([a = b] (mod m)) = (\<exists>k. b = a + m * k)"
   610   apply (unfold zcong_def dvd_def)
   611   apply auto
   612    apply (rule_tac [!] x = "-k" in exI)
   613    apply auto
   614   done
   615 
   616 lemma zgcd_zcong_zgcd:
   617   "0 < m ==>
   618     zgcd (a, m) = 1 ==> [a = b] (mod m) ==> zgcd (b, m) = 1"
   619   apply (auto simp add: zcong_iff_lin)
   620   done
   621 
   622 lemma aux: "a = c ==> b = d ==> a - b = c - (d::int)"
   623   apply auto
   624   done
   625 
   626 lemma aux: "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
   627   apply (rule_tac "s" = "(m * (a div m) + a mod m) - (m * (b div m) + b mod m)"
   628     in trans)
   629    prefer 2
   630    apply (simp add: zdiff_zmult_distrib2)
   631   apply (rule aux)
   632    apply (rule_tac [!] zmod_zdiv_equality)
   633   done
   634 
   635 lemma zcong_zmod: "[a = b] (mod m) = [a mod m = b mod m] (mod m)"
   636   apply (unfold zcong_def)
   637   apply (rule_tac t = "a - b" in ssubst)
   638   apply (rule_tac "m" = "m" in aux)
   639   apply (rule trans)
   640    apply (rule_tac [2] k = m and m = "a div m - b div m" in zdvd_reduce)
   641   apply (simp add: zadd_commute)
   642   done
   643 
   644 lemma zcong_zmod_eq: "0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
   645   apply auto
   646    apply (rule_tac m = m in zcong_zless_imp_eq)
   647        prefer 5
   648        apply (subst zcong_zmod [symmetric])
   649        apply (simp_all add: pos_mod_bound pos_mod_sign)
   650   apply (unfold zcong_def dvd_def)
   651   apply (rule_tac x = "a div m - b div m" in exI)
   652   apply (rule_tac m1 = m in aux [THEN trans])
   653   apply auto
   654   done
   655 
   656 lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
   657   apply (auto simp add: zcong_def)
   658   done
   659 
   660 lemma zcong_zero [iff]: "[a = b] (mod 0) = (a = b)"
   661   apply (auto simp add: zcong_def)
   662   done
   663 
   664 lemma "[a = b] (mod m) = (a mod m = b mod m)"
   665   apply (case_tac "m = 0", simp add: DIVISION_BY_ZERO)
   666   apply (case_tac "0 < m")
   667    apply (simp add: zcong_zmod_eq)
   668   apply (rule_tac t = m in zminus_zminus [THEN subst])
   669   apply (subst zcong_zminus)
   670   apply (subst zcong_zmod_eq)
   671    apply arith
   672   oops  -- {* FIXME: finish this proof? *}
   673 
   674 
   675 subsection {* Modulo *}
   676 
   677 lemma zmod_zdvd_zmod:
   678     "0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
   679   apply (unfold dvd_def)
   680   apply auto
   681   apply (subst zcong_zmod_eq [symmetric])
   682    prefer 2
   683    apply (subst zcong_iff_lin)
   684    apply (rule_tac x = "k * (a div (m * k))" in exI)
   685    apply (subst zadd_commute)
   686    apply (subst zmult_assoc [symmetric])
   687    apply (rule_tac zmod_zdiv_equality)
   688   apply assumption
   689   done
   690 
   691 
   692 subsection {* Extended GCD *}
   693 
   694 declare xzgcda.simps [simp del]
   695 
   696 lemma aux1:
   697   "zgcd (r', r) = k --> 0 < r -->
   698     (\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn))"
   699   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
   700     z = s and aa = t' and ab = t in xzgcda.induct)
   701   apply (subst zgcd_eq)
   702   apply (subst xzgcda.simps)
   703   apply auto
   704   apply (case_tac "r' mod r = 0")
   705    prefer 2
   706    apply (frule_tac a = "r'" in pos_mod_sign)
   707    apply auto
   708   apply (rule exI)
   709   apply (rule exI)
   710   apply (subst xzgcda.simps)
   711   apply auto
   712   apply (simp add: zabs_def)
   713   done
   714 
   715 lemma aux2:
   716   "(\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn)) --> 0 < r -->
   717     zgcd (r', r) = k"
   718   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
   719     z = s and aa = t' and ab = t in xzgcda.induct)
   720   apply (subst zgcd_eq)
   721   apply (subst xzgcda.simps)
   722   apply (auto simp add: linorder_not_le)
   723   apply (case_tac "r' mod r = 0")
   724    prefer 2
   725    apply (frule_tac a = "r'" in pos_mod_sign)
   726    apply auto
   727   apply (erule_tac P = "xzgcda ?u = ?v" in rev_mp)
   728   apply (subst xzgcda.simps)
   729   apply auto
   730   apply (simp add: zabs_def)
   731   done
   732 
   733 lemma xzgcd_correct:
   734     "0 < n ==> (zgcd (m, n) = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
   735   apply (unfold xzgcd_def)
   736   apply (rule iffI)
   737    apply (rule_tac [2] aux2 [THEN mp, THEN mp])
   738     apply (rule aux1 [THEN mp, THEN mp])
   739      apply auto
   740   done
   741 
   742 
   743 text {* \medskip @{term xzgcd} linear *}
   744 
   745 lemma aux:
   746   "(a - r * b) * m + (c - r * d) * (n::int) =
   747     (a * m + c * n) - r * (b * m + d * n)"
   748   apply (simp add: zdiff_zmult_distrib zadd_zmult_distrib2 zmult_assoc)
   749   done
   750 
   751 lemma aux:
   752   "r' = s' * m + t' * n ==> r = s * m + t * n
   753     ==> (r' mod r) = (s' - (r' div r) * s) * m + (t' - (r' div r) * t) * (n::int)"
   754   apply (rule trans)
   755    apply (rule_tac [2] aux [symmetric])
   756   apply simp
   757   apply (subst eq_zdiff_eq)
   758   apply (rule trans [symmetric])
   759   apply (rule_tac b = "s * m + t * n" in zmod_zdiv_equality)
   760   apply (simp add: zmult_commute)
   761   done
   762 
   763 lemma order_le_neq_implies_less: "(x::'a::order) \<le> y ==> x \<noteq> y ==> x < y"
   764   by (rule iffD2 [OF order_less_le conjI])
   765 
   766 lemma xzgcda_linear [rule_format]:
   767   "0 < r --> xzgcda (m, n, r', r, s', s, t', t) = (rn, sn, tn) -->
   768     r' = s' * m + t' * n -->  r = s * m + t * n --> rn = sn * m + tn * n"
   769   apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
   770     z = s and aa = t' and ab = t in xzgcda.induct)
   771   apply (subst xzgcda.simps)
   772   apply (simp (no_asm))
   773   apply (rule impI)+
   774   apply (case_tac "r' mod r = 0")
   775    apply (simp add: xzgcda.simps)
   776    apply clarify
   777   apply (subgoal_tac "0 < r' mod r")
   778    apply (rule_tac [2] order_le_neq_implies_less)
   779    apply (rule_tac [2] pos_mod_sign)
   780     apply (cut_tac m = m and n = n and r' = r' and r = r and s' = s' and
   781       s = s and t' = t' and t = t in aux)
   782       apply auto
   783   done
   784 
   785 lemma xzgcd_linear:
   786     "0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
   787   apply (unfold xzgcd_def)
   788   apply (erule xzgcda_linear)
   789     apply assumption
   790    apply auto
   791   done
   792 
   793 lemma zgcd_ex_linear:
   794     "0 < n ==> zgcd (m, n) = k ==> (\<exists>s t. k = s * m + t * n)"
   795   apply (simp add: xzgcd_correct)
   796   apply safe
   797   apply (rule exI)+
   798   apply (erule xzgcd_linear)
   799   apply auto
   800   done
   801 
   802 lemma zcong_lineq_ex:
   803     "0 < n ==> zgcd (a, n) = 1 ==> \<exists>x. [a * x = 1] (mod n)"
   804   apply (cut_tac m = a and n = n and k = "1" in zgcd_ex_linear)
   805     apply safe
   806   apply (rule_tac x = s in exI)
   807   apply (rule_tac b = "s * a + t * n" in zcong_trans)
   808    prefer 2
   809    apply simp
   810   apply (unfold zcong_def)
   811   apply (simp (no_asm) add: zmult_commute zdvd_zminus_iff)
   812   done
   813 
   814 lemma zcong_lineq_unique:
   815   "0 < n ==>
   816     zgcd (a, n) = 1 ==> \<exists>!x. 0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
   817   apply auto
   818    apply (rule_tac [2] zcong_zless_imp_eq)
   819        apply (tactic {* stac (thm "zcong_cancel2" RS sym) 6 *})
   820          apply (rule_tac [8] zcong_trans)
   821           apply (simp_all (no_asm_simp))
   822    prefer 2
   823    apply (simp add: zcong_sym)
   824   apply (cut_tac a = a and n = n in zcong_lineq_ex)
   825     apply auto
   826   apply (rule_tac x = "x * b mod n" in exI)
   827   apply safe
   828     apply (simp_all (no_asm_simp) add: pos_mod_bound pos_mod_sign)
   829   apply (subst zcong_zmod)
   830   apply (subst zmod_zmult1_eq [symmetric])
   831   apply (subst zcong_zmod [symmetric])
   832   apply (subgoal_tac "[a * x * b = 1 * b] (mod n)")
   833    apply (rule_tac [2] zcong_zmult)
   834     apply (simp_all add: zmult_assoc)
   835   done
   836 
   837 end