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