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