src/HOL/NumberTheory/IntPrimes.thy
author paulson
Mon Oct 22 11:54:22 2001 +0200 (2001-10-22)
changeset 11868 56db9f3a6b3e
parent 11701 3d51fbf81c17
child 13183 c7290200b3f4
permissions -rw-r--r--
Numerals now work for the integers: the binary numerals for 0 and 1 rewrite
to their abstract counterparts, while other binary numerals work correctly.
wenzelm@11049
     1
(*  Title:      HOL/NumberTheory/IntPrimes.thy
paulson@9508
     2
    ID:         $Id$
wenzelm@11049
     3
    Author:     Thomas M. Rasmussen
wenzelm@11049
     4
    Copyright   2000  University of Cambridge
paulson@9508
     5
*)
paulson@9508
     6
wenzelm@11049
     7
header {* Divisibility and prime numbers (on integers) *}
wenzelm@11049
     8
wenzelm@11049
     9
theory IntPrimes = Primes:
wenzelm@11049
    10
wenzelm@11049
    11
text {*
wenzelm@11049
    12
  The @{text dvd} relation, GCD, Euclid's extended algorithm, primes,
wenzelm@11049
    13
  congruences (all on the Integers).  Comparable to theory @{text
wenzelm@11049
    14
  Primes}, but @{text dvd} is included here as it is not present in
wenzelm@11049
    15
  main HOL.  Also includes extended GCD and congruences not present in
wenzelm@11049
    16
  @{text Primes}.
wenzelm@11049
    17
*}
wenzelm@11049
    18
wenzelm@11049
    19
wenzelm@11049
    20
subsection {* Definitions *}
paulson@9508
    21
paulson@9508
    22
consts
wenzelm@11049
    23
  xzgcda :: "int * int * int * int * int * int * int * int => int * int * int"
wenzelm@11049
    24
  xzgcd :: "int => int => int * int * int"
wenzelm@11049
    25
  zprime :: "int set"
wenzelm@11049
    26
  zcong :: "int => int => int => bool"    ("(1[_ = _] '(mod _'))")
wenzelm@11049
    27
wenzelm@11049
    28
recdef xzgcda
wenzelm@11049
    29
  "measure ((\<lambda>(m, n, r', r, s', s, t', t). nat r)
wenzelm@11049
    30
    :: int * int * int * int *int * int * int * int => nat)"
wenzelm@11049
    31
  "xzgcda (m, n, r', r, s', s, t', t) =
paulson@11868
    32
    (if r \<le> 0 then (r', s', t')
wenzelm@11049
    33
     else xzgcda (m, n, r, r' mod r, s, s' - (r' div r) * s, t, t' - (r' div r) * t))"
wenzelm@11049
    34
  (hints simp: pos_mod_bound)
paulson@9508
    35
paulson@9943
    36
constdefs
wenzelm@11049
    37
  zgcd :: "int * int => int"
wenzelm@11049
    38
  "zgcd == \<lambda>(x,y). int (gcd (nat (abs x), nat (abs y)))"
paulson@9943
    39
paulson@9508
    40
defs
paulson@11868
    41
  xzgcd_def: "xzgcd m n == xzgcda (m, n, m, n, 1, 0, 0, 1)"
paulson@11868
    42
  zprime_def: "zprime == {p. 1 < p \<and> (\<forall>m. m dvd p --> m = 1 \<or> m = p)}"
wenzelm@11049
    43
  zcong_def: "[a = b] (mod m) == m dvd (a - b)"
wenzelm@11049
    44
wenzelm@11049
    45
wenzelm@11049
    46
lemma zabs_eq_iff:
paulson@11868
    47
    "(abs (z::int) = w) = (z = w \<and> 0 <= z \<or> z = -w \<and> z < 0)"
wenzelm@11049
    48
  apply (auto simp add: zabs_def)
wenzelm@11049
    49
  done
wenzelm@11049
    50
wenzelm@11049
    51
wenzelm@11049
    52
text {* \medskip @{term gcd} lemmas *}
wenzelm@11049
    53
wenzelm@11049
    54
lemma gcd_add1_eq: "gcd (m + k, k) = gcd (m + k, m)"
wenzelm@11049
    55
  apply (simp add: gcd_commute)
wenzelm@11049
    56
  done
wenzelm@11049
    57
wenzelm@11049
    58
lemma gcd_diff2: "m \<le> n ==> gcd (n, n - m) = gcd (n, m)"
wenzelm@11049
    59
  apply (subgoal_tac "n = m + (n - m)")
wenzelm@11049
    60
   apply (erule ssubst, rule gcd_add1_eq)
wenzelm@11049
    61
  apply simp
wenzelm@11049
    62
  done
wenzelm@11049
    63
wenzelm@11049
    64
wenzelm@11049
    65
subsection {* Divides relation *}
wenzelm@11049
    66
paulson@11868
    67
lemma zdvd_0_right [iff]: "(m::int) dvd 0"
wenzelm@11049
    68
  apply (unfold dvd_def)
wenzelm@11049
    69
  apply (blast intro: zmult_0_right [symmetric])
wenzelm@11049
    70
  done
wenzelm@11049
    71
paulson@11868
    72
lemma zdvd_0_left [iff]: "(0 dvd (m::int)) = (m = 0)"
wenzelm@11049
    73
  apply (unfold dvd_def)
wenzelm@11049
    74
  apply auto
wenzelm@11049
    75
  done
wenzelm@11049
    76
paulson@11868
    77
lemma zdvd_1_left [iff]: "1 dvd (m::int)"
wenzelm@11049
    78
  apply (unfold dvd_def)
wenzelm@11049
    79
  apply simp
wenzelm@11049
    80
  done
wenzelm@11049
    81
wenzelm@11049
    82
lemma zdvd_refl [simp]: "m dvd (m::int)"
wenzelm@11049
    83
  apply (unfold dvd_def)
wenzelm@11049
    84
  apply (blast intro: zmult_1_right [symmetric])
wenzelm@11049
    85
  done
wenzelm@11049
    86
wenzelm@11049
    87
lemma zdvd_trans: "m dvd n ==> n dvd k ==> m dvd (k::int)"
wenzelm@11049
    88
  apply (unfold dvd_def)
wenzelm@11049
    89
  apply (blast intro: zmult_assoc)
wenzelm@11049
    90
  done
wenzelm@11049
    91
wenzelm@11049
    92
lemma zdvd_zminus_iff: "(m dvd -n) = (m dvd (n::int))"
wenzelm@11049
    93
  apply (unfold dvd_def)
wenzelm@11049
    94
  apply auto
wenzelm@11049
    95
   apply (rule_tac [!] x = "-k" in exI)
wenzelm@11049
    96
  apply auto
wenzelm@11049
    97
  done
wenzelm@11049
    98
wenzelm@11049
    99
lemma zdvd_zminus2_iff: "(-m dvd n) = (m dvd (n::int))"
wenzelm@11049
   100
  apply (unfold dvd_def)
wenzelm@11049
   101
  apply auto
wenzelm@11049
   102
   apply (rule_tac [!] x = "-k" in exI)
wenzelm@11049
   103
  apply auto
wenzelm@11049
   104
  done
wenzelm@11049
   105
wenzelm@11049
   106
lemma zdvd_anti_sym:
paulson@11868
   107
    "0 < m ==> 0 < n ==> m dvd n ==> n dvd m ==> m = (n::int)"
wenzelm@11049
   108
  apply (unfold dvd_def)
wenzelm@11049
   109
  apply auto
wenzelm@11049
   110
  apply (simp add: zmult_assoc zmult_eq_self_iff int_0_less_mult_iff zmult_eq_1_iff)
wenzelm@11049
   111
  done
wenzelm@11049
   112
wenzelm@11049
   113
lemma zdvd_zadd: "k dvd m ==> k dvd n ==> k dvd (m + n :: int)"
wenzelm@11049
   114
  apply (unfold dvd_def)
wenzelm@11049
   115
  apply (blast intro: zadd_zmult_distrib2 [symmetric])
wenzelm@11049
   116
  done
wenzelm@11049
   117
wenzelm@11049
   118
lemma zdvd_zdiff: "k dvd m ==> k dvd n ==> k dvd (m - n :: int)"
wenzelm@11049
   119
  apply (unfold dvd_def)
wenzelm@11049
   120
  apply (blast intro: zdiff_zmult_distrib2 [symmetric])
wenzelm@11049
   121
  done
wenzelm@11049
   122
wenzelm@11049
   123
lemma zdvd_zdiffD: "k dvd m - n ==> k dvd n ==> k dvd (m::int)"
wenzelm@11049
   124
  apply (subgoal_tac "m = n + (m - n)")
wenzelm@11049
   125
   apply (erule ssubst)
wenzelm@11049
   126
   apply (blast intro: zdvd_zadd)
wenzelm@11049
   127
  apply simp
wenzelm@11049
   128
  done
wenzelm@11049
   129
wenzelm@11049
   130
lemma zdvd_zmult: "k dvd (n::int) ==> k dvd m * n"
wenzelm@11049
   131
  apply (unfold dvd_def)
wenzelm@11049
   132
  apply (blast intro: zmult_left_commute)
wenzelm@11049
   133
  done
wenzelm@11049
   134
wenzelm@11049
   135
lemma zdvd_zmult2: "k dvd (m::int) ==> k dvd m * n"
wenzelm@11049
   136
  apply (subst zmult_commute)
wenzelm@11049
   137
  apply (erule zdvd_zmult)
wenzelm@11049
   138
  done
wenzelm@11049
   139
wenzelm@11049
   140
lemma [iff]: "(k::int) dvd m * k"
wenzelm@11049
   141
  apply (rule zdvd_zmult)
wenzelm@11049
   142
  apply (rule zdvd_refl)
wenzelm@11049
   143
  done
wenzelm@11049
   144
wenzelm@11049
   145
lemma [iff]: "(k::int) dvd k * m"
wenzelm@11049
   146
  apply (rule zdvd_zmult2)
wenzelm@11049
   147
  apply (rule zdvd_refl)
wenzelm@11049
   148
  done
wenzelm@11049
   149
wenzelm@11049
   150
lemma zdvd_zmultD2: "j * k dvd n ==> j dvd (n::int)"
wenzelm@11049
   151
  apply (unfold dvd_def)
wenzelm@11049
   152
  apply (simp add: zmult_assoc)
wenzelm@11049
   153
  apply blast
wenzelm@11049
   154
  done
wenzelm@11049
   155
wenzelm@11049
   156
lemma zdvd_zmultD: "j * k dvd n ==> k dvd (n::int)"
wenzelm@11049
   157
  apply (rule zdvd_zmultD2)
wenzelm@11049
   158
  apply (subst zmult_commute)
wenzelm@11049
   159
  apply assumption
wenzelm@11049
   160
  done
wenzelm@11049
   161
wenzelm@11049
   162
lemma zdvd_zmult_mono: "i dvd m ==> j dvd (n::int) ==> i * j dvd m * n"
wenzelm@11049
   163
  apply (unfold dvd_def)
wenzelm@11049
   164
  apply clarify
wenzelm@11049
   165
  apply (rule_tac x = "k * ka" in exI)
wenzelm@11049
   166
  apply (simp add: zmult_ac)
wenzelm@11049
   167
  done
wenzelm@11049
   168
wenzelm@11049
   169
lemma zdvd_reduce: "(k dvd n + k * m) = (k dvd (n::int))"
wenzelm@11049
   170
  apply (rule iffI)
wenzelm@11049
   171
   apply (erule_tac [2] zdvd_zadd)
wenzelm@11049
   172
   apply (subgoal_tac "n = (n + k * m) - k * m")
wenzelm@11049
   173
    apply (erule ssubst)
wenzelm@11049
   174
    apply (erule zdvd_zdiff)
wenzelm@11049
   175
    apply simp_all
wenzelm@11049
   176
  done
wenzelm@11049
   177
wenzelm@11049
   178
lemma zdvd_zmod: "f dvd m ==> f dvd (n::int) ==> f dvd m mod n"
wenzelm@11049
   179
  apply (unfold dvd_def)
wenzelm@11049
   180
  apply (auto simp add: zmod_zmult_zmult1)
wenzelm@11049
   181
  done
wenzelm@11049
   182
wenzelm@11049
   183
lemma zdvd_zmod_imp_zdvd: "k dvd m mod n ==> k dvd n ==> k dvd (m::int)"
wenzelm@11049
   184
  apply (subgoal_tac "k dvd n * (m div n) + m mod n")
wenzelm@11049
   185
   apply (simp add: zmod_zdiv_equality [symmetric])
wenzelm@11049
   186
  apply (simp add: zdvd_zadd zdvd_zmult2)
wenzelm@11049
   187
  done
wenzelm@11049
   188
paulson@11868
   189
lemma zdvd_iff_zmod_eq_0: "(k dvd n) = (n mod (k::int) = 0)"
wenzelm@11049
   190
  apply (unfold dvd_def)
wenzelm@11049
   191
  apply auto
wenzelm@11049
   192
  done
wenzelm@11049
   193
paulson@11868
   194
lemma zdvd_not_zless: "0 < m ==> m < n ==> \<not> n dvd (m::int)"
wenzelm@11049
   195
  apply (unfold dvd_def)
wenzelm@11049
   196
  apply auto
paulson@11868
   197
  apply (subgoal_tac "0 < n")
wenzelm@11049
   198
   prefer 2
wenzelm@11049
   199
   apply (blast intro: zless_trans)
wenzelm@11049
   200
  apply (simp add: int_0_less_mult_iff)
paulson@11868
   201
  apply (subgoal_tac "n * k < n * 1")
wenzelm@11049
   202
   apply (drule zmult_zless_cancel1 [THEN iffD1])
wenzelm@11049
   203
   apply auto
wenzelm@11049
   204
  done
wenzelm@11049
   205
wenzelm@11049
   206
lemma int_dvd_iff: "(int m dvd z) = (m dvd nat (abs z))"
wenzelm@11049
   207
  apply (auto simp add: dvd_def nat_abs_mult_distrib)
wenzelm@11049
   208
  apply (auto simp add: nat_eq_iff zabs_eq_iff)
wenzelm@11049
   209
   apply (rule_tac [2] x = "-(int k)" in exI)
wenzelm@11049
   210
  apply (auto simp add: zmult_int [symmetric])
wenzelm@11049
   211
  done
wenzelm@11049
   212
wenzelm@11049
   213
lemma dvd_int_iff: "(z dvd int m) = (nat (abs z) dvd m)"
wenzelm@11049
   214
  apply (auto simp add: dvd_def zabs_def zmult_int [symmetric])
wenzelm@11049
   215
    apply (rule_tac [3] x = "nat k" in exI)
wenzelm@11049
   216
    apply (rule_tac [2] x = "-(int k)" in exI)
wenzelm@11049
   217
    apply (rule_tac x = "nat (-k)" in exI)
wenzelm@11049
   218
    apply (cut_tac [3] k = m in int_less_0_conv)
wenzelm@11049
   219
    apply (cut_tac k = m in int_less_0_conv)
wenzelm@11049
   220
    apply (auto simp add: int_0_le_mult_iff zmult_less_0_iff
wenzelm@11049
   221
      nat_mult_distrib [symmetric] nat_eq_iff2)
wenzelm@11049
   222
  done
wenzelm@11049
   223
paulson@11868
   224
lemma nat_dvd_iff: "(nat z dvd m) = (if 0 \<le> z then (z dvd int m) else m = 0)"
wenzelm@11049
   225
  apply (auto simp add: dvd_def zmult_int [symmetric])
wenzelm@11049
   226
  apply (rule_tac x = "nat k" in exI)
wenzelm@11049
   227
  apply (cut_tac k = m in int_less_0_conv)
wenzelm@11049
   228
  apply (auto simp add: int_0_le_mult_iff zmult_less_0_iff
wenzelm@11049
   229
    nat_mult_distrib [symmetric] nat_eq_iff2)
wenzelm@11049
   230
  done
wenzelm@11049
   231
wenzelm@11049
   232
lemma zminus_dvd_iff [iff]: "(-z dvd w) = (z dvd (w::int))"
wenzelm@11049
   233
  apply (auto simp add: dvd_def)
wenzelm@11049
   234
   apply (rule_tac [!] x = "-k" in exI)
wenzelm@11049
   235
   apply auto
wenzelm@11049
   236
  done
wenzelm@11049
   237
wenzelm@11049
   238
lemma dvd_zminus_iff [iff]: "(z dvd -w) = (z dvd (w::int))"
wenzelm@11049
   239
  apply (auto simp add: dvd_def)
wenzelm@11049
   240
   apply (drule zminus_equation [THEN iffD1])
wenzelm@11049
   241
   apply (rule_tac [!] x = "-k" in exI)
wenzelm@11049
   242
   apply auto
wenzelm@11049
   243
  done
wenzelm@11049
   244
wenzelm@11049
   245
wenzelm@11049
   246
subsection {* Euclid's Algorithm and GCD *}
wenzelm@11049
   247
paulson@11868
   248
lemma zgcd_0 [simp]: "zgcd (m, 0) = abs m"
wenzelm@11049
   249
  apply (simp add: zgcd_def zabs_def)
wenzelm@11049
   250
  done
wenzelm@11049
   251
paulson@11868
   252
lemma zgcd_0_left [simp]: "zgcd (0, m) = abs m"
wenzelm@11049
   253
  apply (simp add: zgcd_def zabs_def)
wenzelm@11049
   254
  done
wenzelm@11049
   255
wenzelm@11049
   256
lemma zgcd_zminus [simp]: "zgcd (-m, n) = zgcd (m, n)"
wenzelm@11049
   257
  apply (simp add: zgcd_def)
wenzelm@11049
   258
  done
wenzelm@11049
   259
wenzelm@11049
   260
lemma zgcd_zminus2 [simp]: "zgcd (m, -n) = zgcd (m, n)"
wenzelm@11049
   261
  apply (simp add: zgcd_def)
wenzelm@11049
   262
  done
wenzelm@11049
   263
paulson@11868
   264
lemma zgcd_non_0: "0 < n ==> zgcd (m, n) = zgcd (n, m mod n)"
wenzelm@11049
   265
  apply (frule_tac b = n and a = m in pos_mod_sign)
wenzelm@11049
   266
  apply (simp add: zgcd_def zabs_def nat_mod_distrib)
wenzelm@11049
   267
  apply (cut_tac a = "-m" and b = n in zmod_zminus1_eq_if)
wenzelm@11049
   268
  apply (auto simp add: gcd_non_0 nat_mod_distrib [symmetric] zmod_zminus1_eq_if)
wenzelm@11049
   269
  apply (frule_tac a = m in pos_mod_bound)
wenzelm@11049
   270
  apply (simp add: nat_diff_distrib)
wenzelm@11049
   271
  apply (rule gcd_diff2)
wenzelm@11049
   272
  apply (simp add: nat_le_eq_zle)
wenzelm@11049
   273
  done
wenzelm@11049
   274
wenzelm@11049
   275
lemma zgcd_eq: "zgcd (m, n) = zgcd (n, m mod n)"
paulson@11868
   276
  apply (tactic {* zdiv_undefined_case_tac "n = 0" 1 *})
wenzelm@11049
   277
  apply (auto simp add: linorder_neq_iff zgcd_non_0)
wenzelm@11049
   278
  apply (cut_tac m = "-m" and n = "-n" in zgcd_non_0)
wenzelm@11049
   279
   apply auto
wenzelm@11049
   280
  done
wenzelm@11049
   281
paulson@11868
   282
lemma zgcd_1 [simp]: "zgcd (m, 1) = 1"
wenzelm@11049
   283
  apply (simp add: zgcd_def zabs_def)
wenzelm@11049
   284
  done
wenzelm@11049
   285
paulson@11868
   286
lemma zgcd_0_1_iff [simp]: "(zgcd (0, m) = 1) = (abs m = 1)"
wenzelm@11049
   287
  apply (simp add: zgcd_def zabs_def)
wenzelm@11049
   288
  done
wenzelm@11049
   289
wenzelm@11049
   290
lemma zgcd_zdvd1 [iff]: "zgcd (m, n) dvd m"
wenzelm@11049
   291
  apply (simp add: zgcd_def zabs_def int_dvd_iff)
wenzelm@11049
   292
  done
wenzelm@11049
   293
wenzelm@11049
   294
lemma zgcd_zdvd2 [iff]: "zgcd (m, n) dvd n"
wenzelm@11049
   295
  apply (simp add: zgcd_def zabs_def int_dvd_iff)
wenzelm@11049
   296
  done
wenzelm@11049
   297
wenzelm@11049
   298
lemma zgcd_greatest_iff: "k dvd zgcd (m, n) = (k dvd m \<and> k dvd n)"
wenzelm@11049
   299
  apply (simp add: zgcd_def zabs_def int_dvd_iff dvd_int_iff nat_dvd_iff)
wenzelm@11049
   300
  done
wenzelm@11049
   301
wenzelm@11049
   302
lemma zgcd_commute: "zgcd (m, n) = zgcd (n, m)"
wenzelm@11049
   303
  apply (simp add: zgcd_def gcd_commute)
wenzelm@11049
   304
  done
wenzelm@11049
   305
paulson@11868
   306
lemma zgcd_1_left [simp]: "zgcd (1, m) = 1"
wenzelm@11049
   307
  apply (simp add: zgcd_def gcd_1_left)
wenzelm@11049
   308
  done
wenzelm@11049
   309
wenzelm@11049
   310
lemma zgcd_assoc: "zgcd (zgcd (k, m), n) = zgcd (k, zgcd (m, n))"
wenzelm@11049
   311
  apply (simp add: zgcd_def gcd_assoc)
wenzelm@11049
   312
  done
wenzelm@11049
   313
wenzelm@11049
   314
lemma zgcd_left_commute: "zgcd (k, zgcd (m, n)) = zgcd (m, zgcd (k, n))"
wenzelm@11049
   315
  apply (rule zgcd_commute [THEN trans])
wenzelm@11049
   316
  apply (rule zgcd_assoc [THEN trans])
wenzelm@11049
   317
  apply (rule zgcd_commute [THEN arg_cong])
wenzelm@11049
   318
  done
wenzelm@11049
   319
wenzelm@11049
   320
lemmas zgcd_ac = zgcd_assoc zgcd_commute zgcd_left_commute
wenzelm@11049
   321
  -- {* addition is an AC-operator *}
wenzelm@11049
   322
paulson@11868
   323
lemma zgcd_zmult_distrib2: "0 \<le> k ==> k * zgcd (m, n) = zgcd (k * m, k * n)"
wenzelm@11049
   324
  apply (simp del: zmult_zminus_right
wenzelm@11049
   325
    add: zmult_zminus_right [symmetric] nat_mult_distrib zgcd_def zabs_def
wenzelm@11049
   326
    zmult_less_0_iff gcd_mult_distrib2 [symmetric] zmult_int [symmetric])
wenzelm@11049
   327
  done
wenzelm@11049
   328
wenzelm@11049
   329
lemma zgcd_zmult_distrib2_abs: "zgcd (k * m, k * n) = abs k * zgcd (m, n)"
wenzelm@11049
   330
  apply (simp add: zabs_def zgcd_zmult_distrib2)
wenzelm@11049
   331
  done
wenzelm@11049
   332
paulson@11868
   333
lemma zgcd_self [simp]: "0 \<le> m ==> zgcd (m, m) = m"
paulson@11868
   334
  apply (cut_tac k = m and m = "1" and n = "1" in zgcd_zmult_distrib2)
wenzelm@11049
   335
   apply simp_all
wenzelm@11049
   336
  done
wenzelm@11049
   337
paulson@11868
   338
lemma zgcd_zmult_eq_self [simp]: "0 \<le> k ==> zgcd (k, k * n) = k"
paulson@11868
   339
  apply (cut_tac k = k and m = "1" and n = n in zgcd_zmult_distrib2)
wenzelm@11049
   340
   apply simp_all
wenzelm@11049
   341
  done
wenzelm@11049
   342
paulson@11868
   343
lemma zgcd_zmult_eq_self2 [simp]: "0 \<le> k ==> zgcd (k * n, k) = k"
paulson@11868
   344
  apply (cut_tac k = k and m = n and n = "1" in zgcd_zmult_distrib2)
wenzelm@11049
   345
   apply simp_all
wenzelm@11049
   346
  done
wenzelm@11049
   347
paulson@11868
   348
lemma aux: "zgcd (n, k) = 1 ==> k dvd m * n ==> 0 \<le> m ==> k dvd m"
wenzelm@11049
   349
  apply (subgoal_tac "m = zgcd (m * n, m * k)")
wenzelm@11049
   350
   apply (erule ssubst, rule zgcd_greatest_iff [THEN iffD2])
wenzelm@11049
   351
   apply (simp_all add: zgcd_zmult_distrib2 [symmetric] int_0_le_mult_iff)
wenzelm@11049
   352
  done
wenzelm@11049
   353
paulson@11868
   354
lemma zrelprime_zdvd_zmult: "zgcd (n, k) = 1 ==> k dvd m * n ==> k dvd m"
paulson@11868
   355
  apply (case_tac "0 \<le> m")
wenzelm@11049
   356
   apply (blast intro: aux)
wenzelm@11049
   357
  apply (subgoal_tac "k dvd -m")
wenzelm@11049
   358
   apply (rule_tac [2] aux)
wenzelm@11049
   359
     apply auto
wenzelm@11049
   360
  done
wenzelm@11049
   361
wenzelm@11049
   362
lemma zprime_imp_zrelprime:
paulson@11868
   363
    "p \<in> zprime ==> \<not> p dvd n ==> zgcd (n, p) = 1"
wenzelm@11049
   364
  apply (unfold zprime_def)
wenzelm@11049
   365
  apply auto
wenzelm@11049
   366
  done
wenzelm@11049
   367
wenzelm@11049
   368
lemma zless_zprime_imp_zrelprime:
paulson@11868
   369
    "p \<in> zprime ==> 0 < n ==> n < p ==> zgcd (n, p) = 1"
wenzelm@11049
   370
  apply (erule zprime_imp_zrelprime)
wenzelm@11049
   371
  apply (erule zdvd_not_zless)
wenzelm@11049
   372
  apply assumption
wenzelm@11049
   373
  done
wenzelm@11049
   374
wenzelm@11049
   375
lemma zprime_zdvd_zmult:
paulson@11868
   376
    "0 \<le> (m::int) ==> p \<in> zprime ==> p dvd m * n ==> p dvd m \<or> p dvd n"
wenzelm@11049
   377
  apply safe
wenzelm@11049
   378
  apply (rule zrelprime_zdvd_zmult)
wenzelm@11049
   379
   apply (rule zprime_imp_zrelprime)
wenzelm@11049
   380
    apply auto
wenzelm@11049
   381
  done
wenzelm@11049
   382
wenzelm@11049
   383
lemma zgcd_zadd_zmult [simp]: "zgcd (m + n * k, n) = zgcd (m, n)"
wenzelm@11049
   384
  apply (rule zgcd_eq [THEN trans])
wenzelm@11049
   385
  apply (simp add: zmod_zadd1_eq)
wenzelm@11049
   386
  apply (rule zgcd_eq [symmetric])
wenzelm@11049
   387
  done
wenzelm@11049
   388
wenzelm@11049
   389
lemma zgcd_zdvd_zgcd_zmult: "zgcd (m, n) dvd zgcd (k * m, n)"
wenzelm@11049
   390
  apply (simp add: zgcd_greatest_iff)
wenzelm@11049
   391
  apply (blast intro: zdvd_trans)
wenzelm@11049
   392
  done
wenzelm@11049
   393
wenzelm@11049
   394
lemma zgcd_zmult_zdvd_zgcd:
paulson@11868
   395
    "zgcd (k, n) = 1 ==> zgcd (k * m, n) dvd zgcd (m, n)"
wenzelm@11049
   396
  apply (simp add: zgcd_greatest_iff)
wenzelm@11049
   397
  apply (rule_tac n = k in zrelprime_zdvd_zmult)
wenzelm@11049
   398
   prefer 2
wenzelm@11049
   399
   apply (simp add: zmult_commute)
wenzelm@11049
   400
  apply (subgoal_tac "zgcd (k, zgcd (k * m, n)) = zgcd (k * m, zgcd (k, n))")
wenzelm@11049
   401
   apply simp
wenzelm@11049
   402
  apply (simp (no_asm) add: zgcd_ac)
wenzelm@11049
   403
  done
wenzelm@11049
   404
paulson@11868
   405
lemma zgcd_zmult_cancel: "zgcd (k, n) = 1 ==> zgcd (k * m, n) = zgcd (m, n)"
wenzelm@11049
   406
  apply (simp add: zgcd_def nat_abs_mult_distrib gcd_mult_cancel)
wenzelm@11049
   407
  done
wenzelm@11049
   408
wenzelm@11049
   409
lemma zgcd_zgcd_zmult:
paulson@11868
   410
    "zgcd (k, m) = 1 ==> zgcd (n, m) = 1 ==> zgcd (k * n, m) = 1"
wenzelm@11049
   411
  apply (simp (no_asm_simp) add: zgcd_zmult_cancel)
wenzelm@11049
   412
  done
wenzelm@11049
   413
paulson@11868
   414
lemma zdvd_iff_zgcd: "0 < m ==> (m dvd n) = (zgcd (n, m) = m)"
wenzelm@11049
   415
  apply safe
wenzelm@11049
   416
   apply (rule_tac [2] n = "zgcd (n, m)" in zdvd_trans)
wenzelm@11049
   417
    apply (rule_tac [3] zgcd_zdvd1)
wenzelm@11049
   418
   apply simp_all
wenzelm@11049
   419
  apply (unfold dvd_def)
wenzelm@11049
   420
  apply auto
wenzelm@11049
   421
  done
wenzelm@11049
   422
wenzelm@11049
   423
wenzelm@11049
   424
subsection {* Congruences *}
wenzelm@11049
   425
paulson@11868
   426
lemma zcong_1 [simp]: "[a = b] (mod 1)"
wenzelm@11049
   427
  apply (unfold zcong_def)
wenzelm@11049
   428
  apply auto
wenzelm@11049
   429
  done
wenzelm@11049
   430
wenzelm@11049
   431
lemma zcong_refl [simp]: "[k = k] (mod m)"
wenzelm@11049
   432
  apply (unfold zcong_def)
wenzelm@11049
   433
  apply auto
wenzelm@11049
   434
  done
paulson@9508
   435
wenzelm@11049
   436
lemma zcong_sym: "[a = b] (mod m) = [b = a] (mod m)"
wenzelm@11049
   437
  apply (unfold zcong_def dvd_def)
wenzelm@11049
   438
  apply auto
wenzelm@11049
   439
   apply (rule_tac [!] x = "-k" in exI)
wenzelm@11049
   440
   apply auto
wenzelm@11049
   441
  done
wenzelm@11049
   442
wenzelm@11049
   443
lemma zcong_zadd:
wenzelm@11049
   444
    "[a = b] (mod m) ==> [c = d] (mod m) ==> [a + c = b + d] (mod m)"
wenzelm@11049
   445
  apply (unfold zcong_def)
wenzelm@11049
   446
  apply (rule_tac s = "(a - b) + (c - d)" in subst)
wenzelm@11049
   447
   apply (rule_tac [2] zdvd_zadd)
wenzelm@11049
   448
    apply auto
wenzelm@11049
   449
  done
wenzelm@11049
   450
wenzelm@11049
   451
lemma zcong_zdiff:
wenzelm@11049
   452
    "[a = b] (mod m) ==> [c = d] (mod m) ==> [a - c = b - d] (mod m)"
wenzelm@11049
   453
  apply (unfold zcong_def)
wenzelm@11049
   454
  apply (rule_tac s = "(a - b) - (c - d)" in subst)
wenzelm@11049
   455
   apply (rule_tac [2] zdvd_zdiff)
wenzelm@11049
   456
    apply auto
wenzelm@11049
   457
  done
wenzelm@11049
   458
wenzelm@11049
   459
lemma zcong_trans:
wenzelm@11049
   460
    "[a = b] (mod m) ==> [b = c] (mod m) ==> [a = c] (mod m)"
wenzelm@11049
   461
  apply (unfold zcong_def dvd_def)
wenzelm@11049
   462
  apply auto
wenzelm@11049
   463
  apply (rule_tac x = "k + ka" in exI)
wenzelm@11049
   464
  apply (simp add: zadd_ac zadd_zmult_distrib2)
wenzelm@11049
   465
  done
wenzelm@11049
   466
wenzelm@11049
   467
lemma zcong_zmult:
wenzelm@11049
   468
    "[a = b] (mod m) ==> [c = d] (mod m) ==> [a * c = b * d] (mod m)"
wenzelm@11049
   469
  apply (rule_tac b = "b * c" in zcong_trans)
wenzelm@11049
   470
   apply (unfold zcong_def)
wenzelm@11049
   471
   apply (rule_tac s = "c * (a - b)" in subst)
wenzelm@11049
   472
    apply (rule_tac [3] s = "b * (c - d)" in subst)
wenzelm@11049
   473
     prefer 4
wenzelm@11049
   474
     apply (blast intro: zdvd_zmult)
wenzelm@11049
   475
    prefer 2
wenzelm@11049
   476
    apply (blast intro: zdvd_zmult)
wenzelm@11049
   477
   apply (simp_all add: zdiff_zmult_distrib2 zmult_commute)
wenzelm@11049
   478
  done
wenzelm@11049
   479
wenzelm@11049
   480
lemma zcong_scalar: "[a = b] (mod m) ==> [a * k = b * k] (mod m)"
wenzelm@11049
   481
  apply (rule zcong_zmult)
wenzelm@11049
   482
  apply simp_all
wenzelm@11049
   483
  done
wenzelm@11049
   484
wenzelm@11049
   485
lemma zcong_scalar2: "[a = b] (mod m) ==> [k * a = k * b] (mod m)"
wenzelm@11049
   486
  apply (rule zcong_zmult)
wenzelm@11049
   487
  apply simp_all
wenzelm@11049
   488
  done
wenzelm@11049
   489
wenzelm@11049
   490
lemma zcong_zmult_self: "[a * m = b * m] (mod m)"
wenzelm@11049
   491
  apply (unfold zcong_def)
wenzelm@11049
   492
  apply (rule zdvd_zdiff)
wenzelm@11049
   493
   apply simp_all
wenzelm@11049
   494
  done
wenzelm@11049
   495
wenzelm@11049
   496
lemma zcong_square:
paulson@11868
   497
  "p \<in> zprime ==> 0 < a ==> [a * a = 1] (mod p)
paulson@11868
   498
    ==> [a = 1] (mod p) \<or> [a = p - 1] (mod p)"
wenzelm@11049
   499
  apply (unfold zcong_def)
wenzelm@11049
   500
  apply (rule zprime_zdvd_zmult)
paulson@11868
   501
    apply (rule_tac [3] s = "a * a - 1 + p * (1 - a)" in subst)
wenzelm@11049
   502
     prefer 4
wenzelm@11049
   503
     apply (simp add: zdvd_reduce)
wenzelm@11049
   504
    apply (simp_all add: zdiff_zmult_distrib zmult_commute zdiff_zmult_distrib2)
wenzelm@11049
   505
  done
wenzelm@11049
   506
wenzelm@11049
   507
lemma zcong_cancel:
paulson@11868
   508
  "0 \<le> m ==>
paulson@11868
   509
    zgcd (k, m) = 1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
wenzelm@11049
   510
  apply safe
wenzelm@11049
   511
   prefer 2
wenzelm@11049
   512
   apply (blast intro: zcong_scalar)
wenzelm@11049
   513
  apply (case_tac "b < a")
wenzelm@11049
   514
   prefer 2
wenzelm@11049
   515
   apply (subst zcong_sym)
wenzelm@11049
   516
   apply (unfold zcong_def)
wenzelm@11049
   517
   apply (rule_tac [!] zrelprime_zdvd_zmult)
wenzelm@11049
   518
     apply (simp_all add: zdiff_zmult_distrib)
wenzelm@11049
   519
  apply (subgoal_tac "m dvd (-(a * k - b * k))")
wenzelm@11049
   520
   apply (simp add: zminus_zdiff_eq)
wenzelm@11049
   521
  apply (subst zdvd_zminus_iff)
wenzelm@11049
   522
  apply assumption
wenzelm@11049
   523
  done
wenzelm@11049
   524
wenzelm@11049
   525
lemma zcong_cancel2:
paulson@11868
   526
  "0 \<le> m ==>
paulson@11868
   527
    zgcd (k, m) = 1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
wenzelm@11049
   528
  apply (simp add: zmult_commute zcong_cancel)
wenzelm@11049
   529
  done
wenzelm@11049
   530
wenzelm@11049
   531
lemma zcong_zgcd_zmult_zmod:
paulson@11868
   532
  "[a = b] (mod m) ==> [a = b] (mod n) ==> zgcd (m, n) = 1
wenzelm@11049
   533
    ==> [a = b] (mod m * n)"
wenzelm@11049
   534
  apply (unfold zcong_def dvd_def)
wenzelm@11049
   535
  apply auto
wenzelm@11049
   536
  apply (subgoal_tac "m dvd n * ka")
wenzelm@11049
   537
   apply (subgoal_tac "m dvd ka")
paulson@11868
   538
    apply (case_tac [2] "0 \<le> ka")
wenzelm@11049
   539
     prefer 3
wenzelm@11049
   540
     apply (subst zdvd_zminus_iff [symmetric])
wenzelm@11049
   541
     apply (rule_tac n = n in zrelprime_zdvd_zmult)
wenzelm@11049
   542
      apply (simp add: zgcd_commute)
wenzelm@11049
   543
     apply (simp add: zmult_commute zdvd_zminus_iff)
wenzelm@11049
   544
    prefer 2
wenzelm@11049
   545
    apply (rule_tac n = n in zrelprime_zdvd_zmult)
wenzelm@11049
   546
     apply (simp add: zgcd_commute)
wenzelm@11049
   547
    apply (simp add: zmult_commute)
wenzelm@11049
   548
   apply (auto simp add: dvd_def)
wenzelm@11049
   549
  apply (blast intro: sym)
wenzelm@11049
   550
  done
wenzelm@11049
   551
wenzelm@11049
   552
lemma zcong_zless_imp_eq:
paulson@11868
   553
  "0 \<le> a ==>
paulson@11868
   554
    a < m ==> 0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
wenzelm@11049
   555
  apply (unfold zcong_def dvd_def)
wenzelm@11049
   556
  apply auto
wenzelm@11049
   557
  apply (drule_tac f = "\<lambda>z. z mod m" in arg_cong)
wenzelm@11049
   558
  apply (cut_tac z = a and w = b in zless_linear)
wenzelm@11049
   559
  apply auto
wenzelm@11049
   560
   apply (subgoal_tac [2] "(a - b) mod m = a - b")
wenzelm@11049
   561
    apply (rule_tac [3] mod_pos_pos_trivial)
wenzelm@11049
   562
     apply auto
wenzelm@11049
   563
  apply (subgoal_tac "(m + (a - b)) mod m = m + (a - b)")
wenzelm@11049
   564
   apply (rule_tac [2] mod_pos_pos_trivial)
wenzelm@11049
   565
    apply auto
wenzelm@11049
   566
  done
wenzelm@11049
   567
wenzelm@11049
   568
lemma zcong_square_zless:
paulson@11868
   569
  "p \<in> zprime ==> 0 < a ==> a < p ==>
paulson@11868
   570
    [a * a = 1] (mod p) ==> a = 1 \<or> a = p - 1"
wenzelm@11049
   571
  apply (cut_tac p = p and a = a in zcong_square)
wenzelm@11049
   572
     apply (simp add: zprime_def)
wenzelm@11049
   573
    apply (auto intro: zcong_zless_imp_eq)
wenzelm@11049
   574
  done
wenzelm@11049
   575
wenzelm@11049
   576
lemma zcong_not:
paulson@11868
   577
    "0 < a ==> a < m ==> 0 < b ==> b < a ==> \<not> [a = b] (mod m)"
wenzelm@11049
   578
  apply (unfold zcong_def)
wenzelm@11049
   579
  apply (rule zdvd_not_zless)
wenzelm@11049
   580
   apply auto
wenzelm@11049
   581
  done
wenzelm@11049
   582
wenzelm@11049
   583
lemma zcong_zless_0:
paulson@11868
   584
    "0 \<le> a ==> a < m ==> [a = 0] (mod m) ==> a = 0"
wenzelm@11049
   585
  apply (unfold zcong_def dvd_def)
wenzelm@11049
   586
  apply auto
paulson@11868
   587
  apply (subgoal_tac "0 < m")
wenzelm@11049
   588
   apply (rotate_tac -1)
wenzelm@11049
   589
   apply (simp add: int_0_le_mult_iff)
paulson@11868
   590
   apply (subgoal_tac "m * k < m * 1")
wenzelm@11049
   591
    apply (drule zmult_zless_cancel1 [THEN iffD1])
wenzelm@11049
   592
    apply (auto simp add: linorder_neq_iff)
wenzelm@11049
   593
  done
wenzelm@11049
   594
wenzelm@11049
   595
lemma zcong_zless_unique:
paulson@11868
   596
    "0 < m ==> (\<exists>!b. 0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
wenzelm@11049
   597
  apply auto
wenzelm@11049
   598
   apply (subgoal_tac [2] "[b = y] (mod m)")
paulson@11868
   599
    apply (case_tac [2] "b = 0")
paulson@11868
   600
     apply (case_tac [3] "y = 0")
wenzelm@11049
   601
      apply (auto intro: zcong_trans zcong_zless_0 zcong_zless_imp_eq order_less_le
wenzelm@11049
   602
        simp add: zcong_sym)
wenzelm@11049
   603
  apply (unfold zcong_def dvd_def)
wenzelm@11049
   604
  apply (rule_tac x = "a mod m" in exI)
wenzelm@11049
   605
  apply (auto simp add: pos_mod_sign pos_mod_bound)
wenzelm@11049
   606
  apply (rule_tac x = "-(a div m)" in exI)
wenzelm@11049
   607
  apply (cut_tac a = a and b = m in zmod_zdiv_equality)
wenzelm@11049
   608
  apply auto
wenzelm@11049
   609
  done
wenzelm@11049
   610
wenzelm@11049
   611
lemma zcong_iff_lin: "([a = b] (mod m)) = (\<exists>k. b = a + m * k)"
wenzelm@11049
   612
  apply (unfold zcong_def dvd_def)
wenzelm@11049
   613
  apply auto
wenzelm@11049
   614
   apply (rule_tac [!] x = "-k" in exI)
wenzelm@11049
   615
   apply auto
wenzelm@11049
   616
  done
wenzelm@11049
   617
wenzelm@11049
   618
lemma zgcd_zcong_zgcd:
paulson@11868
   619
  "0 < m ==>
paulson@11868
   620
    zgcd (a, m) = 1 ==> [a = b] (mod m) ==> zgcd (b, m) = 1"
wenzelm@11049
   621
  apply (auto simp add: zcong_iff_lin)
wenzelm@11049
   622
  done
wenzelm@11049
   623
wenzelm@11049
   624
lemma aux: "a = c ==> b = d ==> a - b = c - (d::int)"
wenzelm@11049
   625
  apply auto
wenzelm@11049
   626
  done
wenzelm@11049
   627
wenzelm@11049
   628
lemma aux: "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
wenzelm@11049
   629
  apply (rule_tac "s" = "(m * (a div m) + a mod m) - (m * (b div m) + b mod m)"
wenzelm@11049
   630
    in trans)
wenzelm@11049
   631
   prefer 2
wenzelm@11049
   632
   apply (simp add: zdiff_zmult_distrib2)
wenzelm@11049
   633
  apply (rule aux)
wenzelm@11049
   634
   apply (rule_tac [!] zmod_zdiv_equality)
wenzelm@11049
   635
  done
paulson@9508
   636
wenzelm@11049
   637
lemma zcong_zmod: "[a = b] (mod m) = [a mod m = b mod m] (mod m)"
wenzelm@11049
   638
  apply (unfold zcong_def)
wenzelm@11049
   639
  apply (rule_tac t = "a - b" in ssubst)
wenzelm@11049
   640
  apply (rule_tac "m" = "m" in aux)
wenzelm@11049
   641
  apply (rule trans)
wenzelm@11049
   642
   apply (rule_tac [2] k = m and m = "a div m - b div m" in zdvd_reduce)
wenzelm@11049
   643
  apply (simp add: zadd_commute)
wenzelm@11049
   644
  done
wenzelm@11049
   645
paulson@11868
   646
lemma zcong_zmod_eq: "0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
wenzelm@11049
   647
  apply auto
wenzelm@11049
   648
   apply (rule_tac m = m in zcong_zless_imp_eq)
wenzelm@11049
   649
       prefer 5
wenzelm@11049
   650
       apply (subst zcong_zmod [symmetric])
wenzelm@11049
   651
       apply (simp_all add: pos_mod_bound pos_mod_sign)
wenzelm@11049
   652
  apply (unfold zcong_def dvd_def)
wenzelm@11049
   653
  apply (rule_tac x = "a div m - b div m" in exI)
wenzelm@11049
   654
  apply (rule_tac m1 = m in aux [THEN trans])
wenzelm@11049
   655
  apply auto
wenzelm@11049
   656
  done
wenzelm@11049
   657
wenzelm@11049
   658
lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
wenzelm@11049
   659
  apply (auto simp add: zcong_def)
wenzelm@11049
   660
  done
wenzelm@11049
   661
paulson@11868
   662
lemma zcong_zero [iff]: "[a = b] (mod 0) = (a = b)"
wenzelm@11049
   663
  apply (auto simp add: zcong_def)
wenzelm@11049
   664
  done
wenzelm@11049
   665
wenzelm@11049
   666
lemma "[a = b] (mod m) = (a mod m = b mod m)"
paulson@11868
   667
  apply (tactic {* zdiv_undefined_case_tac "m = 0" 1 *})
paulson@11868
   668
  apply (case_tac "0 < m")
wenzelm@11049
   669
   apply (simp add: zcong_zmod_eq)
wenzelm@11049
   670
  apply (rule_tac t = m in zminus_zminus [THEN subst])
wenzelm@11049
   671
  apply (subst zcong_zminus)
wenzelm@11049
   672
  apply (subst zcong_zmod_eq)
wenzelm@11049
   673
   apply arith
wenzelm@11049
   674
  oops  -- {* FIXME: finish this proof? *}
wenzelm@11049
   675
wenzelm@11049
   676
wenzelm@11049
   677
subsection {* Modulo *}
wenzelm@11049
   678
wenzelm@11049
   679
lemma zmod_zdvd_zmod:
paulson@11868
   680
    "0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
wenzelm@11049
   681
  apply (unfold dvd_def)
wenzelm@11049
   682
  apply auto
wenzelm@11049
   683
  apply (subst zcong_zmod_eq [symmetric])
wenzelm@11049
   684
   prefer 2
wenzelm@11049
   685
   apply (subst zcong_iff_lin)
wenzelm@11049
   686
   apply (rule_tac x = "k * (a div (m * k))" in exI)
wenzelm@11049
   687
   apply (subst zadd_commute)
wenzelm@11049
   688
   apply (subst zmult_assoc [symmetric])
wenzelm@11049
   689
   apply (rule_tac zmod_zdiv_equality)
wenzelm@11049
   690
  apply assumption
wenzelm@11049
   691
  done
wenzelm@11049
   692
wenzelm@11049
   693
wenzelm@11049
   694
subsection {* Extended GCD *}
wenzelm@11049
   695
wenzelm@11049
   696
declare xzgcda.simps [simp del]
wenzelm@11049
   697
wenzelm@11049
   698
lemma aux1:
paulson@11868
   699
  "zgcd (r', r) = k --> 0 < r -->
wenzelm@11049
   700
    (\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn))"
wenzelm@11049
   701
  apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
wenzelm@11049
   702
    z = s and aa = t' and ab = t in xzgcda.induct)
wenzelm@11049
   703
  apply (subst zgcd_eq)
wenzelm@11049
   704
  apply (subst xzgcda.simps)
wenzelm@11049
   705
  apply auto
paulson@11868
   706
  apply (case_tac "r' mod r = 0")
wenzelm@11049
   707
   prefer 2
wenzelm@11049
   708
   apply (frule_tac a = "r'" in pos_mod_sign)
wenzelm@11049
   709
   apply auto
wenzelm@11049
   710
   apply arith
wenzelm@11049
   711
  apply (rule exI)
wenzelm@11049
   712
  apply (rule exI)
wenzelm@11049
   713
  apply (subst xzgcda.simps)
wenzelm@11049
   714
  apply auto
wenzelm@11049
   715
  apply (simp add: zabs_def)
wenzelm@11049
   716
  done
wenzelm@11049
   717
wenzelm@11049
   718
lemma aux2:
paulson@11868
   719
  "(\<exists>sn tn. xzgcda (m, n, r', r, s', s, t', t) = (k, sn, tn)) --> 0 < r -->
wenzelm@11049
   720
    zgcd (r', r) = k"
wenzelm@11049
   721
  apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
wenzelm@11049
   722
    z = s and aa = t' and ab = t in xzgcda.induct)
wenzelm@11049
   723
  apply (subst zgcd_eq)
wenzelm@11049
   724
  apply (subst xzgcda.simps)
wenzelm@11049
   725
  apply (auto simp add: linorder_not_le)
paulson@11868
   726
  apply (case_tac "r' mod r = 0")
wenzelm@11049
   727
   prefer 2
wenzelm@11049
   728
   apply (frule_tac a = "r'" in pos_mod_sign)
wenzelm@11049
   729
   apply auto
wenzelm@11049
   730
   apply arith
wenzelm@11049
   731
  apply (erule_tac P = "xzgcda ?u = ?v" in rev_mp)
wenzelm@11049
   732
  apply (subst xzgcda.simps)
wenzelm@11049
   733
  apply auto
wenzelm@11049
   734
  apply (simp add: zabs_def)
wenzelm@11049
   735
  done
wenzelm@11049
   736
wenzelm@11049
   737
lemma xzgcd_correct:
paulson@11868
   738
    "0 < n ==> (zgcd (m, n) = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
wenzelm@11049
   739
  apply (unfold xzgcd_def)
wenzelm@11049
   740
  apply (rule iffI)
wenzelm@11049
   741
   apply (rule_tac [2] aux2 [THEN mp, THEN mp])
wenzelm@11049
   742
    apply (rule aux1 [THEN mp, THEN mp])
wenzelm@11049
   743
     apply auto
wenzelm@11049
   744
  done
wenzelm@11049
   745
wenzelm@11049
   746
wenzelm@11049
   747
text {* \medskip @{term xzgcd} linear *}
wenzelm@11049
   748
wenzelm@11049
   749
lemma aux:
wenzelm@11049
   750
  "(a - r * b) * m + (c - r * d) * (n::int) =
wenzelm@11049
   751
    (a * m + c * n) - r * (b * m + d * n)"
wenzelm@11049
   752
  apply (simp add: zdiff_zmult_distrib zadd_zmult_distrib2 zmult_assoc)
wenzelm@11049
   753
  done
wenzelm@11049
   754
wenzelm@11049
   755
lemma aux:
wenzelm@11049
   756
  "r' = s' * m + t' * n ==> r = s * m + t * n
wenzelm@11049
   757
    ==> (r' mod r) = (s' - (r' div r) * s) * m + (t' - (r' div r) * t) * (n::int)"
wenzelm@11049
   758
  apply (rule trans)
wenzelm@11049
   759
   apply (rule_tac [2] aux [symmetric])
wenzelm@11049
   760
  apply simp
wenzelm@11049
   761
  apply (subst eq_zdiff_eq)
wenzelm@11049
   762
  apply (rule trans [symmetric])
wenzelm@11049
   763
  apply (rule_tac b = "s * m + t * n" in zmod_zdiv_equality)
wenzelm@11049
   764
  apply (simp add: zmult_commute)
wenzelm@11049
   765
  done
wenzelm@11049
   766
wenzelm@11049
   767
lemma order_le_neq_implies_less: "(x::'a::order) \<le> y ==> x \<noteq> y ==> x < y"
wenzelm@11049
   768
  by (rule iffD2 [OF order_less_le conjI])
wenzelm@11049
   769
wenzelm@11049
   770
lemma xzgcda_linear [rule_format]:
paulson@11868
   771
  "0 < r --> xzgcda (m, n, r', r, s', s, t', t) = (rn, sn, tn) -->
wenzelm@11049
   772
    r' = s' * m + t' * n -->  r = s * m + t * n --> rn = sn * m + tn * n"
wenzelm@11049
   773
  apply (rule_tac u = m and v = n and w = r' and x = r and y = s' and
wenzelm@11049
   774
    z = s and aa = t' and ab = t in xzgcda.induct)
wenzelm@11049
   775
  apply (subst xzgcda.simps)
wenzelm@11049
   776
  apply (simp (no_asm))
wenzelm@11049
   777
  apply (rule impI)+
paulson@11868
   778
  apply (case_tac "r' mod r = 0")
wenzelm@11049
   779
   apply (simp add: xzgcda.simps)
wenzelm@11049
   780
   apply clarify
paulson@11868
   781
  apply (subgoal_tac "0 < r' mod r")
wenzelm@11049
   782
   apply (rule_tac [2] order_le_neq_implies_less)
wenzelm@11049
   783
   apply (rule_tac [2] pos_mod_sign)
wenzelm@11049
   784
    apply (cut_tac m = m and n = n and r' = r' and r = r and s' = s' and
wenzelm@11049
   785
      s = s and t' = t' and t = t in aux)
wenzelm@11049
   786
      apply auto
wenzelm@11049
   787
  done
wenzelm@11049
   788
wenzelm@11049
   789
lemma xzgcd_linear:
paulson@11868
   790
    "0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
wenzelm@11049
   791
  apply (unfold xzgcd_def)
wenzelm@11049
   792
  apply (erule xzgcda_linear)
wenzelm@11049
   793
    apply assumption
wenzelm@11049
   794
   apply auto
wenzelm@11049
   795
  done
wenzelm@11049
   796
wenzelm@11049
   797
lemma zgcd_ex_linear:
paulson@11868
   798
    "0 < n ==> zgcd (m, n) = k ==> (\<exists>s t. k = s * m + t * n)"
wenzelm@11049
   799
  apply (simp add: xzgcd_correct)
wenzelm@11049
   800
  apply safe
wenzelm@11049
   801
  apply (rule exI)+
wenzelm@11049
   802
  apply (erule xzgcd_linear)
wenzelm@11049
   803
  apply auto
wenzelm@11049
   804
  done
wenzelm@11049
   805
wenzelm@11049
   806
lemma zcong_lineq_ex:
paulson@11868
   807
    "0 < n ==> zgcd (a, n) = 1 ==> \<exists>x. [a * x = 1] (mod n)"
paulson@11868
   808
  apply (cut_tac m = a and n = n and k = "1" in zgcd_ex_linear)
wenzelm@11049
   809
    apply safe
wenzelm@11049
   810
  apply (rule_tac x = s in exI)
wenzelm@11049
   811
  apply (rule_tac b = "s * a + t * n" in zcong_trans)
wenzelm@11049
   812
   prefer 2
wenzelm@11049
   813
   apply simp
wenzelm@11049
   814
  apply (unfold zcong_def)
wenzelm@11049
   815
  apply (simp (no_asm) add: zmult_commute zdvd_zminus_iff)
wenzelm@11049
   816
  done
wenzelm@11049
   817
wenzelm@11049
   818
lemma zcong_lineq_unique:
paulson@11868
   819
  "0 < n ==>
paulson@11868
   820
    zgcd (a, n) = 1 ==> \<exists>!x. 0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
wenzelm@11049
   821
  apply auto
wenzelm@11049
   822
   apply (rule_tac [2] zcong_zless_imp_eq)
wenzelm@11049
   823
       apply (tactic {* stac (thm "zcong_cancel2" RS sym) 6 *})
wenzelm@11049
   824
         apply (rule_tac [8] zcong_trans)
wenzelm@11049
   825
          apply (simp_all (no_asm_simp))
wenzelm@11049
   826
   prefer 2
wenzelm@11049
   827
   apply (simp add: zcong_sym)
wenzelm@11049
   828
  apply (cut_tac a = a and n = n in zcong_lineq_ex)
wenzelm@11049
   829
    apply auto
wenzelm@11049
   830
  apply (rule_tac x = "x * b mod n" in exI)
wenzelm@11049
   831
  apply safe
wenzelm@11049
   832
    apply (simp_all (no_asm_simp) add: pos_mod_bound pos_mod_sign)
wenzelm@11049
   833
  apply (subst zcong_zmod)
wenzelm@11049
   834
  apply (subst zmod_zmult1_eq [symmetric])
wenzelm@11049
   835
  apply (subst zcong_zmod [symmetric])
paulson@11868
   836
  apply (subgoal_tac "[a * x * b = 1 * b] (mod n)")
wenzelm@11049
   837
   apply (rule_tac [2] zcong_zmult)
wenzelm@11049
   838
    apply (simp_all add: zmult_assoc)
wenzelm@11049
   839
  done
paulson@9508
   840
paulson@9508
   841
end