src/HOL/Old_Number_Theory/IntPrimes.thy
author bulwahn
Fri Oct 21 11:17:14 2011 +0200 (2011-10-21)
changeset 45231 d85a2fdc586c
parent 44766 d4d33a4d7548
child 47162 9d7d919b9fd8
permissions -rw-r--r--
replacing code_inline by code_unfold, removing obsolete code_unfold, code_inline del now that the ancient code generator is removed
wenzelm@38159
     1
(*  Title:      HOL/Old_Number_Theory/IntPrimes.thy
wenzelm@38159
     2
    Author:     Thomas M. Rasmussen
wenzelm@11049
     3
    Copyright   2000  University of Cambridge
paulson@9508
     4
*)
paulson@9508
     5
wenzelm@11049
     6
header {* Divisibility and prime numbers (on integers) *}
wenzelm@11049
     7
haftmann@25596
     8
theory IntPrimes
wenzelm@38159
     9
imports Primes
haftmann@25596
    10
begin
wenzelm@11049
    11
wenzelm@11049
    12
text {*
wenzelm@11049
    13
  The @{text dvd} relation, GCD, Euclid's extended algorithm, primes,
wenzelm@11049
    14
  congruences (all on the Integers).  Comparable to theory @{text
wenzelm@11049
    15
  Primes}, but @{text dvd} is included here as it is not present in
wenzelm@11049
    16
  main HOL.  Also includes extended GCD and congruences not present in
wenzelm@11049
    17
  @{text Primes}.
wenzelm@11049
    18
*}
wenzelm@11049
    19
wenzelm@11049
    20
wenzelm@11049
    21
subsection {* Definitions *}
paulson@9508
    22
wenzelm@38159
    23
fun xzgcda :: "int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int => (int * int * int)"
krauss@35440
    24
where
krauss@35440
    25
  "xzgcda m n r' r s' s t' t =
wenzelm@32960
    26
        (if r \<le> 0 then (r', s', t')
krauss@35440
    27
         else xzgcda m n r (r' mod r) 
krauss@35440
    28
                      s (s' - (r' div r) * s) 
krauss@35440
    29
                      t (t' - (r' div r) * t))"
paulson@9508
    30
wenzelm@38159
    31
definition zprime :: "int \<Rightarrow> bool"
wenzelm@38159
    32
  where "zprime p = (1 < p \<and> (\<forall>m. 0 <= m & m dvd p --> m = 1 \<or> m = p))"
paulson@13833
    33
wenzelm@38159
    34
definition xzgcd :: "int => int => int * int * int"
wenzelm@38159
    35
  where "xzgcd m n = xzgcda m n m n 1 0 0 1"
paulson@13833
    36
wenzelm@38159
    37
definition zcong :: "int => int => int => bool"  ("(1[_ = _] '(mod _'))")
wenzelm@38159
    38
  where "[a = b] (mod m) = (m dvd (a - b))"
wenzelm@38159
    39
wenzelm@11049
    40
wenzelm@11049
    41
subsection {* Euclid's Algorithm and GCD *}
wenzelm@11049
    42
wenzelm@11049
    43
paulson@13833
    44
lemma zrelprime_zdvd_zmult_aux:
haftmann@27556
    45
     "zgcd n k = 1 ==> k dvd m * n ==> 0 \<le> m ==> k dvd m"
huffman@44766
    46
    by (metis abs_of_nonneg dvd_triv_right zgcd_greatest_iff zgcd_zmult_distrib2_abs mult_1_right)
wenzelm@11049
    47
haftmann@27556
    48
lemma zrelprime_zdvd_zmult: "zgcd n k = 1 ==> k dvd m * n ==> k dvd m"
paulson@11868
    49
  apply (case_tac "0 \<le> m")
wenzelm@13524
    50
   apply (blast intro: zrelprime_zdvd_zmult_aux)
wenzelm@11049
    51
  apply (subgoal_tac "k dvd -m")
paulson@13833
    52
   apply (rule_tac [2] zrelprime_zdvd_zmult_aux, auto)
wenzelm@11049
    53
  done
wenzelm@11049
    54
haftmann@27556
    55
lemma zgcd_geq_zero: "0 <= zgcd x y"
paulson@13833
    56
  by (auto simp add: zgcd_def)
paulson@13833
    57
paulson@13837
    58
text{*This is merely a sanity check on zprime, since the previous version
paulson@13837
    59
      denoted the empty set.*}
nipkow@16663
    60
lemma "zprime 2"
paulson@13837
    61
  apply (auto simp add: zprime_def) 
paulson@13837
    62
  apply (frule zdvd_imp_le, simp) 
paulson@13837
    63
  apply (auto simp add: order_le_less dvd_def) 
paulson@13837
    64
  done
paulson@13837
    65
wenzelm@11049
    66
lemma zprime_imp_zrelprime:
haftmann@27556
    67
    "zprime p ==> \<not> p dvd n ==> zgcd n p = 1"
paulson@13833
    68
  apply (auto simp add: zprime_def)
nipkow@30042
    69
  apply (metis zgcd_geq_zero zgcd_zdvd1 zgcd_zdvd2)
wenzelm@11049
    70
  done
wenzelm@11049
    71
wenzelm@11049
    72
lemma zless_zprime_imp_zrelprime:
haftmann@27556
    73
    "zprime p ==> 0 < n ==> n < p ==> zgcd n p = 1"
wenzelm@11049
    74
  apply (erule zprime_imp_zrelprime)
paulson@13833
    75
  apply (erule zdvd_not_zless, assumption)
wenzelm@11049
    76
  done
wenzelm@11049
    77
wenzelm@11049
    78
lemma zprime_zdvd_zmult:
nipkow@16663
    79
    "0 \<le> (m::int) ==> zprime p ==> p dvd m * n ==> p dvd m \<or> p dvd n"
chaieb@27569
    80
  by (metis zgcd_zdvd1 zgcd_zdvd2 zgcd_pos zprime_def zrelprime_dvd_mult)
wenzelm@11049
    81
haftmann@27556
    82
lemma zgcd_zadd_zmult [simp]: "zgcd (m + n * k) n = zgcd m n"
wenzelm@11049
    83
  apply (rule zgcd_eq [THEN trans])
nipkow@29948
    84
  apply (simp add: mod_add_eq)
wenzelm@11049
    85
  apply (rule zgcd_eq [symmetric])
wenzelm@11049
    86
  done
wenzelm@11049
    87
haftmann@27556
    88
lemma zgcd_zdvd_zgcd_zmult: "zgcd m n dvd zgcd (k * m) n"
nipkow@30042
    89
by (simp add: zgcd_greatest_iff)
wenzelm@11049
    90
wenzelm@11049
    91
lemma zgcd_zmult_zdvd_zgcd:
chaieb@27569
    92
    "zgcd k n = 1 ==> zgcd (k * m) n dvd zgcd m n"
wenzelm@11049
    93
  apply (simp add: zgcd_greatest_iff)
wenzelm@11049
    94
  apply (rule_tac n = k in zrelprime_zdvd_zmult)
wenzelm@11049
    95
   prefer 2
huffman@44766
    96
   apply (simp add: mult_commute)
paulson@23839
    97
  apply (metis zgcd_1 zgcd_commute zgcd_left_commute)
wenzelm@11049
    98
  done
wenzelm@11049
    99
haftmann@27556
   100
lemma zgcd_zmult_cancel: "zgcd k n = 1 ==> zgcd (k * m) n = zgcd m n"
paulson@13833
   101
  by (simp add: zgcd_def nat_abs_mult_distrib gcd_mult_cancel)
wenzelm@11049
   102
wenzelm@11049
   103
lemma zgcd_zgcd_zmult:
chaieb@27569
   104
    "zgcd k m = 1 ==> zgcd n m = 1 ==> zgcd (k * n) m = 1"
paulson@13833
   105
  by (simp add: zgcd_zmult_cancel)
wenzelm@11049
   106
haftmann@27556
   107
lemma zdvd_iff_zgcd: "0 < m ==> m dvd n \<longleftrightarrow> zgcd n m = m"
paulson@23839
   108
  by (metis abs_of_pos zdvd_mult_div_cancel zgcd_0 zgcd_commute zgcd_geq_zero zgcd_zdvd2 zgcd_zmult_eq_self)
paulson@23839
   109
wenzelm@11049
   110
wenzelm@11049
   111
wenzelm@11049
   112
subsection {* Congruences *}
wenzelm@11049
   113
paulson@11868
   114
lemma zcong_1 [simp]: "[a = b] (mod 1)"
paulson@13833
   115
  by (unfold zcong_def, auto)
wenzelm@11049
   116
wenzelm@11049
   117
lemma zcong_refl [simp]: "[k = k] (mod m)"
paulson@13833
   118
  by (unfold zcong_def, auto)
paulson@9508
   119
wenzelm@11049
   120
lemma zcong_sym: "[a = b] (mod m) = [b = a] (mod m)"
nipkow@30042
   121
  unfolding zcong_def minus_diff_eq [of a, symmetric] dvd_minus_iff ..
wenzelm@11049
   122
wenzelm@11049
   123
lemma zcong_zadd:
wenzelm@11049
   124
    "[a = b] (mod m) ==> [c = d] (mod m) ==> [a + c = b + d] (mod m)"
wenzelm@11049
   125
  apply (unfold zcong_def)
wenzelm@11049
   126
  apply (rule_tac s = "(a - b) + (c - d)" in subst)
nipkow@30042
   127
   apply (rule_tac [2] dvd_add, auto)
wenzelm@11049
   128
  done
wenzelm@11049
   129
wenzelm@11049
   130
lemma zcong_zdiff:
wenzelm@11049
   131
    "[a = b] (mod m) ==> [c = d] (mod m) ==> [a - c = b - d] (mod m)"
wenzelm@11049
   132
  apply (unfold zcong_def)
wenzelm@11049
   133
  apply (rule_tac s = "(a - b) - (c - d)" in subst)
nipkow@30042
   134
   apply (rule_tac [2] dvd_diff, auto)
wenzelm@11049
   135
  done
wenzelm@11049
   136
wenzelm@11049
   137
lemma zcong_trans:
nipkow@29925
   138
  "[a = b] (mod m) ==> [b = c] (mod m) ==> [a = c] (mod m)"
nipkow@29925
   139
unfolding zcong_def by (auto elim!: dvdE simp add: algebra_simps)
wenzelm@11049
   140
wenzelm@11049
   141
lemma zcong_zmult:
wenzelm@11049
   142
    "[a = b] (mod m) ==> [c = d] (mod m) ==> [a * c = b * d] (mod m)"
wenzelm@11049
   143
  apply (rule_tac b = "b * c" in zcong_trans)
wenzelm@11049
   144
   apply (unfold zcong_def)
huffman@44766
   145
  apply (metis right_diff_distrib dvd_mult mult_commute)
huffman@44766
   146
  apply (metis right_diff_distrib dvd_mult)
wenzelm@11049
   147
  done
wenzelm@11049
   148
wenzelm@11049
   149
lemma zcong_scalar: "[a = b] (mod m) ==> [a * k = b * k] (mod m)"
paulson@13833
   150
  by (rule zcong_zmult, simp_all)
wenzelm@11049
   151
wenzelm@11049
   152
lemma zcong_scalar2: "[a = b] (mod m) ==> [k * a = k * b] (mod m)"
paulson@13833
   153
  by (rule zcong_zmult, simp_all)
wenzelm@11049
   154
wenzelm@11049
   155
lemma zcong_zmult_self: "[a * m = b * m] (mod m)"
wenzelm@11049
   156
  apply (unfold zcong_def)
nipkow@30042
   157
  apply (rule dvd_diff, simp_all)
wenzelm@11049
   158
  done
wenzelm@11049
   159
wenzelm@11049
   160
lemma zcong_square:
nipkow@16663
   161
   "[| zprime p;  0 < a;  [a * a = 1] (mod p)|]
paulson@11868
   162
    ==> [a = 1] (mod p) \<or> [a = p - 1] (mod p)"
wenzelm@11049
   163
  apply (unfold zcong_def)
wenzelm@11049
   164
  apply (rule zprime_zdvd_zmult)
paulson@11868
   165
    apply (rule_tac [3] s = "a * a - 1 + p * (1 - a)" in subst)
wenzelm@11049
   166
     prefer 4
wenzelm@11049
   167
     apply (simp add: zdvd_reduce)
huffman@44766
   168
    apply (simp_all add: left_diff_distrib mult_commute right_diff_distrib)
wenzelm@11049
   169
  done
wenzelm@11049
   170
wenzelm@11049
   171
lemma zcong_cancel:
paulson@11868
   172
  "0 \<le> m ==>
haftmann@27556
   173
    zgcd k m = 1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
wenzelm@11049
   174
  apply safe
wenzelm@11049
   175
   prefer 2
wenzelm@11049
   176
   apply (blast intro: zcong_scalar)
wenzelm@11049
   177
  apply (case_tac "b < a")
wenzelm@11049
   178
   prefer 2
wenzelm@11049
   179
   apply (subst zcong_sym)
wenzelm@11049
   180
   apply (unfold zcong_def)
wenzelm@11049
   181
   apply (rule_tac [!] zrelprime_zdvd_zmult)
huffman@44766
   182
     apply (simp_all add: left_diff_distrib)
wenzelm@11049
   183
  apply (subgoal_tac "m dvd (-(a * k - b * k))")
paulson@14271
   184
   apply simp
nipkow@30042
   185
  apply (subst dvd_minus_iff, assumption)
wenzelm@11049
   186
  done
wenzelm@11049
   187
wenzelm@11049
   188
lemma zcong_cancel2:
paulson@11868
   189
  "0 \<le> m ==>
haftmann@27556
   190
    zgcd k m = 1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
huffman@44766
   191
  by (simp add: mult_commute zcong_cancel)
wenzelm@11049
   192
wenzelm@11049
   193
lemma zcong_zgcd_zmult_zmod:
haftmann@27556
   194
  "[a = b] (mod m) ==> [a = b] (mod n) ==> zgcd m n = 1
wenzelm@11049
   195
    ==> [a = b] (mod m * n)"
haftmann@27651
   196
  apply (auto simp add: zcong_def dvd_def)
wenzelm@11049
   197
  apply (subgoal_tac "m dvd n * ka")
wenzelm@11049
   198
   apply (subgoal_tac "m dvd ka")
paulson@11868
   199
    apply (case_tac [2] "0 \<le> ka")
huffman@44766
   200
  apply (metis zdvd_mult_div_cancel dvd_refl dvd_mult_left mult_commute zrelprime_zdvd_zmult)
huffman@44766
   201
  apply (metis abs_dvd_iff abs_of_nonneg add_0 zgcd_0_left zgcd_commute zgcd_zadd_zmult zgcd_zdvd_zgcd_zmult zgcd_zmult_distrib2_abs mult_1_right mult_commute)
huffman@44766
   202
  apply (metis mult_le_0_iff  zdvd_mono zdvd_mult_cancel dvd_triv_left zero_le_mult_iff order_antisym linorder_linear order_refl mult_commute zrelprime_zdvd_zmult)
nipkow@30042
   203
  apply (metis dvd_triv_left)
wenzelm@11049
   204
  done
wenzelm@11049
   205
wenzelm@11049
   206
lemma zcong_zless_imp_eq:
paulson@11868
   207
  "0 \<le> a ==>
paulson@11868
   208
    a < m ==> 0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
paulson@13833
   209
  apply (unfold zcong_def dvd_def, auto)
wenzelm@11049
   210
  apply (drule_tac f = "\<lambda>z. z mod m" in arg_cong)
huffman@44766
   211
  apply (metis diff_add_cancel mod_pos_pos_trivial add_0 add_commute zmod_eq_0_iff mod_add_right_eq)
wenzelm@11049
   212
  done
wenzelm@11049
   213
wenzelm@11049
   214
lemma zcong_square_zless:
nipkow@16663
   215
  "zprime p ==> 0 < a ==> a < p ==>
paulson@11868
   216
    [a * a = 1] (mod p) ==> a = 1 \<or> a = p - 1"
wenzelm@11049
   217
  apply (cut_tac p = p and a = a in zcong_square)
wenzelm@11049
   218
     apply (simp add: zprime_def)
wenzelm@11049
   219
    apply (auto intro: zcong_zless_imp_eq)
wenzelm@11049
   220
  done
wenzelm@11049
   221
wenzelm@11049
   222
lemma zcong_not:
paulson@11868
   223
    "0 < a ==> a < m ==> 0 < b ==> b < a ==> \<not> [a = b] (mod m)"
wenzelm@11049
   224
  apply (unfold zcong_def)
paulson@13833
   225
  apply (rule zdvd_not_zless, auto)
wenzelm@11049
   226
  done
wenzelm@11049
   227
wenzelm@11049
   228
lemma zcong_zless_0:
paulson@11868
   229
    "0 \<le> a ==> a < m ==> [a = 0] (mod m) ==> a = 0"
paulson@13833
   230
  apply (unfold zcong_def dvd_def, auto)
nipkow@30042
   231
  apply (metis div_pos_pos_trivial linorder_not_less div_mult_self1_is_id)
wenzelm@11049
   232
  done
wenzelm@11049
   233
wenzelm@11049
   234
lemma zcong_zless_unique:
paulson@11868
   235
    "0 < m ==> (\<exists>!b. 0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
wenzelm@11049
   236
  apply auto
paulson@23839
   237
   prefer 2 apply (metis zcong_sym zcong_trans zcong_zless_imp_eq)
wenzelm@11049
   238
  apply (unfold zcong_def dvd_def)
paulson@13833
   239
  apply (rule_tac x = "a mod m" in exI, auto)
paulson@23839
   240
  apply (metis zmult_div_cancel)
wenzelm@11049
   241
  done
wenzelm@11049
   242
wenzelm@11049
   243
lemma zcong_iff_lin: "([a = b] (mod m)) = (\<exists>k. b = a + m * k)"
haftmann@27651
   244
  unfolding zcong_def
nipkow@29667
   245
  apply (auto elim!: dvdE simp add: algebra_simps)
haftmann@27651
   246
  apply (rule_tac x = "-k" in exI) apply simp
wenzelm@11049
   247
  done
wenzelm@11049
   248
wenzelm@11049
   249
lemma zgcd_zcong_zgcd:
paulson@11868
   250
  "0 < m ==>
haftmann@27556
   251
    zgcd a m = 1 ==> [a = b] (mod m) ==> zgcd b m = 1"
paulson@13833
   252
  by (auto simp add: zcong_iff_lin)
wenzelm@11049
   253
paulson@13833
   254
lemma zcong_zmod_aux:
paulson@13833
   255
     "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
huffman@44766
   256
  by(simp add: right_diff_distrib add_diff_eq eq_diff_eq add_ac)
nipkow@13517
   257
wenzelm@11049
   258
lemma zcong_zmod: "[a = b] (mod m) = [a mod m = b mod m] (mod m)"
wenzelm@11049
   259
  apply (unfold zcong_def)
wenzelm@11049
   260
  apply (rule_tac t = "a - b" in ssubst)
ballarin@14174
   261
  apply (rule_tac m = m in zcong_zmod_aux)
wenzelm@11049
   262
  apply (rule trans)
wenzelm@11049
   263
   apply (rule_tac [2] k = m and m = "a div m - b div m" in zdvd_reduce)
huffman@44766
   264
  apply (simp add: add_commute)
wenzelm@11049
   265
  done
wenzelm@11049
   266
paulson@11868
   267
lemma zcong_zmod_eq: "0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
wenzelm@11049
   268
  apply auto
paulson@23839
   269
  apply (metis pos_mod_conj zcong_zless_imp_eq zcong_zmod)
paulson@23839
   270
  apply (metis zcong_refl zcong_zmod)
wenzelm@11049
   271
  done
wenzelm@11049
   272
wenzelm@11049
   273
lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
paulson@13833
   274
  by (auto simp add: zcong_def)
wenzelm@11049
   275
paulson@11868
   276
lemma zcong_zero [iff]: "[a = b] (mod 0) = (a = b)"
paulson@13833
   277
  by (auto simp add: zcong_def)
wenzelm@11049
   278
wenzelm@11049
   279
lemma "[a = b] (mod m) = (a mod m = b mod m)"
wenzelm@41541
   280
  apply (cases "m = 0", simp)
paulson@13193
   281
  apply (simp add: linorder_neq_iff)
paulson@13193
   282
  apply (erule disjE)  
paulson@13193
   283
   prefer 2 apply (simp add: zcong_zmod_eq)
paulson@13193
   284
  txt{*Remainding case: @{term "m<0"}*}
huffman@44766
   285
  apply (rule_tac t = m in minus_minus [THEN subst])
wenzelm@11049
   286
  apply (subst zcong_zminus)
paulson@13833
   287
  apply (subst zcong_zmod_eq, arith)
paulson@13193
   288
  apply (frule neg_mod_bound [of _ a], frule neg_mod_bound [of _ b]) 
nipkow@13788
   289
  apply (simp add: zmod_zminus2_eq_if del: neg_mod_bound)
paulson@13193
   290
  done
wenzelm@11049
   291
wenzelm@11049
   292
subsection {* Modulo *}
wenzelm@11049
   293
wenzelm@11049
   294
lemma zmod_zdvd_zmod:
paulson@11868
   295
    "0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
nipkow@30034
   296
  by (rule mod_mod_cancel) 
wenzelm@11049
   297
wenzelm@11049
   298
wenzelm@11049
   299
subsection {* Extended GCD *}
wenzelm@11049
   300
wenzelm@11049
   301
declare xzgcda.simps [simp del]
wenzelm@11049
   302
wenzelm@13524
   303
lemma xzgcd_correct_aux1:
haftmann@27556
   304
  "zgcd r' r = k --> 0 < r -->
krauss@35440
   305
    (\<exists>sn tn. xzgcda m n r' r s' s t' t = (k, sn, tn))"
krauss@35440
   306
  apply (induct m n r' r s' s t' t rule: xzgcda.induct)
wenzelm@11049
   307
  apply (subst zgcd_eq)
paulson@13833
   308
  apply (subst xzgcda.simps, auto)
wenzelm@24759
   309
  apply (case_tac "r' mod r = 0")
wenzelm@24759
   310
   prefer 2
wenzelm@24759
   311
   apply (frule_tac a = "r'" in pos_mod_sign, auto)
wenzelm@24759
   312
  apply (rule exI)
wenzelm@24759
   313
  apply (rule exI)
wenzelm@24759
   314
  apply (subst xzgcda.simps, auto)
wenzelm@11049
   315
  done
wenzelm@11049
   316
wenzelm@13524
   317
lemma xzgcd_correct_aux2:
krauss@35440
   318
  "(\<exists>sn tn. xzgcda m n r' r s' s t' t = (k, sn, tn)) --> 0 < r -->
haftmann@27556
   319
    zgcd r' r = k"
krauss@35440
   320
  apply (induct m n r' r s' s t' t rule: xzgcda.induct)
wenzelm@11049
   321
  apply (subst zgcd_eq)
wenzelm@11049
   322
  apply (subst xzgcda.simps)
wenzelm@11049
   323
  apply (auto simp add: linorder_not_le)
paulson@11868
   324
  apply (case_tac "r' mod r = 0")
wenzelm@11049
   325
   prefer 2
paulson@13833
   326
   apply (frule_tac a = "r'" in pos_mod_sign, auto)
huffman@44766
   327
  apply (metis Pair_eq xzgcda.simps order_refl)
wenzelm@11049
   328
  done
wenzelm@11049
   329
wenzelm@11049
   330
lemma xzgcd_correct:
chaieb@27569
   331
    "0 < n ==> (zgcd m n = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
wenzelm@11049
   332
  apply (unfold xzgcd_def)
wenzelm@11049
   333
  apply (rule iffI)
wenzelm@13524
   334
   apply (rule_tac [2] xzgcd_correct_aux2 [THEN mp, THEN mp])
paulson@13833
   335
    apply (rule xzgcd_correct_aux1 [THEN mp, THEN mp], auto)
wenzelm@11049
   336
  done
wenzelm@11049
   337
wenzelm@11049
   338
wenzelm@11049
   339
text {* \medskip @{term xzgcd} linear *}
wenzelm@11049
   340
wenzelm@13524
   341
lemma xzgcda_linear_aux1:
wenzelm@11049
   342
  "(a - r * b) * m + (c - r * d) * (n::int) =
paulson@13833
   343
   (a * m + c * n) - r * (b * m + d * n)"
huffman@44766
   344
  by (simp add: left_diff_distrib right_distrib mult_assoc)
wenzelm@11049
   345
wenzelm@13524
   346
lemma xzgcda_linear_aux2:
wenzelm@11049
   347
  "r' = s' * m + t' * n ==> r = s * m + t * n
wenzelm@11049
   348
    ==> (r' mod r) = (s' - (r' div r) * s) * m + (t' - (r' div r) * t) * (n::int)"
wenzelm@11049
   349
  apply (rule trans)
wenzelm@13524
   350
   apply (rule_tac [2] xzgcda_linear_aux1 [symmetric])
paulson@14271
   351
  apply (simp add: eq_diff_eq mult_commute)
wenzelm@11049
   352
  done
wenzelm@11049
   353
wenzelm@11049
   354
lemma order_le_neq_implies_less: "(x::'a::order) \<le> y ==> x \<noteq> y ==> x < y"
wenzelm@11049
   355
  by (rule iffD2 [OF order_less_le conjI])
wenzelm@11049
   356
wenzelm@11049
   357
lemma xzgcda_linear [rule_format]:
krauss@35440
   358
  "0 < r --> xzgcda m n r' r s' s t' t = (rn, sn, tn) -->
wenzelm@11049
   359
    r' = s' * m + t' * n -->  r = s * m + t * n --> rn = sn * m + tn * n"
krauss@35440
   360
  apply (induct m n r' r s' s t' t rule: xzgcda.induct)
wenzelm@11049
   361
  apply (subst xzgcda.simps)
wenzelm@11049
   362
  apply (simp (no_asm))
wenzelm@11049
   363
  apply (rule impI)+
paulson@11868
   364
  apply (case_tac "r' mod r = 0")
paulson@13833
   365
   apply (simp add: xzgcda.simps, clarify)
paulson@11868
   366
  apply (subgoal_tac "0 < r' mod r")
wenzelm@11049
   367
   apply (rule_tac [2] order_le_neq_implies_less)
wenzelm@11049
   368
   apply (rule_tac [2] pos_mod_sign)
wenzelm@11049
   369
    apply (cut_tac m = m and n = n and r' = r' and r = r and s' = s' and
paulson@13833
   370
      s = s and t' = t' and t = t in xzgcda_linear_aux2, auto)
wenzelm@11049
   371
  done
wenzelm@11049
   372
wenzelm@11049
   373
lemma xzgcd_linear:
paulson@11868
   374
    "0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
wenzelm@11049
   375
  apply (unfold xzgcd_def)
paulson@13837
   376
  apply (erule xzgcda_linear, assumption, auto)
wenzelm@11049
   377
  done
wenzelm@11049
   378
wenzelm@11049
   379
lemma zgcd_ex_linear:
haftmann@27556
   380
    "0 < n ==> zgcd m n = k ==> (\<exists>s t. k = s * m + t * n)"
paulson@13833
   381
  apply (simp add: xzgcd_correct, safe)
wenzelm@11049
   382
  apply (rule exI)+
paulson@13833
   383
  apply (erule xzgcd_linear, auto)
wenzelm@11049
   384
  done
wenzelm@11049
   385
wenzelm@11049
   386
lemma zcong_lineq_ex:
haftmann@27556
   387
    "0 < n ==> zgcd a n = 1 ==> \<exists>x. [a * x = 1] (mod n)"
paulson@13833
   388
  apply (cut_tac m = a and n = n and k = 1 in zgcd_ex_linear, safe)
wenzelm@11049
   389
  apply (rule_tac x = s in exI)
wenzelm@11049
   390
  apply (rule_tac b = "s * a + t * n" in zcong_trans)
wenzelm@11049
   391
   prefer 2
wenzelm@11049
   392
   apply simp
wenzelm@11049
   393
  apply (unfold zcong_def)
huffman@44766
   394
  apply (simp (no_asm) add: mult_commute)
wenzelm@11049
   395
  done
wenzelm@11049
   396
wenzelm@11049
   397
lemma zcong_lineq_unique:
paulson@11868
   398
  "0 < n ==>
haftmann@27556
   399
    zgcd a n = 1 ==> \<exists>!x. 0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
wenzelm@11049
   400
  apply auto
wenzelm@11049
   401
   apply (rule_tac [2] zcong_zless_imp_eq)
wenzelm@39159
   402
       apply (tactic {* stac (@{thm zcong_cancel2} RS sym) 6 *})
wenzelm@11049
   403
         apply (rule_tac [8] zcong_trans)
wenzelm@11049
   404
          apply (simp_all (no_asm_simp))
wenzelm@11049
   405
   prefer 2
wenzelm@11049
   406
   apply (simp add: zcong_sym)
paulson@13833
   407
  apply (cut_tac a = a and n = n in zcong_lineq_ex, auto)
paulson@13833
   408
  apply (rule_tac x = "x * b mod n" in exI, safe)
nipkow@13788
   409
    apply (simp_all (no_asm_simp))
huffman@44766
   410
  apply (metis zcong_scalar zcong_zmod zmod_zmult1_eq mult_1 mult_assoc)
wenzelm@11049
   411
  done
paulson@9508
   412
paulson@9508
   413
end