1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 (* This file was automatically generated: do not edit *********************)
19 (*#***********************************************************************)
21 (* v * The Coq Proof Assistant / The Coq Development Team *)
23 (* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
25 (* \VV/ **************************************************************)
27 (* // * This file is distributed under the terms of the *)
29 (* * GNU Lesser General Public License Version 2.1 *)
31 (*#***********************************************************************)
33 (*i $Id: Znumtheory.v,v 1.5.2.1 2004/07/16 19:31:22 herbelin Exp $ i*)
35 include "ZArith/ZArith_base.ma".
37 include "ZArith/Zcomplements.ma".
39 include "ZArith/Zdiv.ma".
42 Open Local Scope Z_scope.
45 (*#* This file contains some notions of number theory upon Z numbers:
46 - a divisibility predicate [Zdivide]
47 - a gcd predicate [gcd]
48 - Euclid algorithm [euclid]
49 - an efficient [Zgcd] function
50 - a relatively prime predicate [rel_prime]
51 - a prime predicate [prime]
54 (*#* * Divisibility *)
56 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide.ind".
58 (*#* Syntax for divisibility *)
61 Notation "( a | b )" := (Zdivide a b) (at level 0) : Z_scope.
64 (*#* Results concerning divisibility*)
66 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_refl.con" as lemma.
68 inline procedural "cic:/Coq/ZArith/Znumtheory/Zone_divide.con" as lemma.
70 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_0.con" as lemma.
73 Hint Resolve Zdivide_refl Zone_divide Zdivide_0: zarith.
76 inline procedural "cic:/Coq/ZArith/Znumtheory/Zmult_divide_compat_l.con" as lemma.
78 inline procedural "cic:/Coq/ZArith/Znumtheory/Zmult_divide_compat_r.con" as lemma.
81 Hint Resolve Zmult_divide_compat_l Zmult_divide_compat_r: zarith.
84 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_plus_r.con" as lemma.
86 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_opp_r.con" as lemma.
88 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_opp_r_rev.con" as lemma.
90 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_opp_l.con" as lemma.
92 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_opp_l_rev.con" as lemma.
94 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_minus_l.con" as lemma.
96 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_mult_l.con" as lemma.
98 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_mult_r.con" as lemma.
100 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_factor_r.con" as lemma.
102 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_factor_l.con" as lemma.
105 Hint Resolve Zdivide_plus_r Zdivide_opp_r Zdivide_opp_r_rev Zdivide_opp_l
106 Zdivide_opp_l_rev Zdivide_minus_l Zdivide_mult_l Zdivide_mult_r
107 Zdivide_factor_r Zdivide_factor_l: zarith.
110 (*#* Auxiliary result. *)
112 inline procedural "cic:/Coq/ZArith/Znumtheory/Zmult_one.con" as lemma.
114 (*#* Only [1] and [-1] divide [1]. *)
116 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_1.con" as lemma.
118 (*#* If [a] divides [b] and [b] divides [a] then [a] is [b] or [-b]. *)
120 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_antisym.con" as lemma.
122 (*#* If [a] divides [b] and [b<>0] then [|a| <= |b|]. *)
124 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_bounds.con" as lemma.
126 (*#* * Greatest common divisor (gcd). *)
128 (*#* There is no unicity of the gcd; hence we define the predicate [gcd a b d]
129 expressing that [d] is a gcd of [a] and [b].
130 (We show later that the [gcd] is actually unique if we discard its sign.) *)
132 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd.ind".
134 (*#* Trivial properties of [gcd] *)
136 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_sym.con" as lemma.
138 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_0.con" as lemma.
140 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_minus.con" as lemma.
142 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_opp.con" as lemma.
145 Hint Resolve Zis_gcd_sym Zis_gcd_0 Zis_gcd_minus Zis_gcd_opp: zarith.
148 (*#* * Extended Euclid algorithm. *)
150 (*#* Euclid's algorithm to compute the [gcd] mainly relies on
151 the following property. *)
153 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_for_euclid.con" as lemma.
155 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_for_euclid2.con" as lemma.
157 (*#* We implement the extended version of Euclid's algorithm,
158 i.e. the one computing Bezout's coefficients as it computes
159 the [gcd]. We follow the algorithm given in Knuth's
160 "Art of Computer Programming", vol 2, page 325. *)
163 Section extended_euclid_algorithm
167 cic:/Coq/ZArith/Znumtheory/extended_euclid_algorithm/a.var
171 cic:/Coq/ZArith/Znumtheory/extended_euclid_algorithm/b.var
174 (*#* The specification of Euclid's algorithm is the existence of
175 [u], [v] and [d] such that [ua+vb=d] and [(gcd a b d)]. *)
177 inline procedural "cic:/Coq/ZArith/Znumtheory/Euclid.ind".
179 (*#* The recursive part of Euclid's algorithm uses well-founded
180 recursion of non-negative integers. It maintains 6 integers
181 [u1,u2,u3,v1,v2,v3] such that the following invariant holds:
182 [u1*a+u2*b=u3] and [v1*a+v2*b=v3] and [gcd(u2,v3)=gcd(a,b)].
185 inline procedural "cic:/Coq/ZArith/Znumtheory/euclid_rec.con" as lemma.
187 (*#* We get Euclid's algorithm by applying [euclid_rec] on
188 [1,0,a,0,1,b] when [b>=0] and [1,0,a,0,-1,-b] when [b<0]. *)
190 inline procedural "cic:/Coq/ZArith/Znumtheory/euclid.con" as lemma.
193 End extended_euclid_algorithm
196 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_uniqueness_apart_sign.con" as theorem.
198 (*#* * Bezout's coefficients *)
200 inline procedural "cic:/Coq/ZArith/Znumtheory/Bezout.ind".
202 (*#* Existence of Bezout's coefficients for the [gcd] of [a] and [b] *)
204 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_bezout.con" as lemma.
206 (*#* gcd of [ca] and [cb] is [c gcd(a,b)]. *)
208 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_mult.con" as lemma.
210 (*#* We could obtain a [Zgcd] function via [euclid]. But we propose
211 here a more direct version of a [Zgcd], with better extraction
212 (no bezout coeffs). *)
214 inline procedural "cic:/Coq/ZArith/Znumtheory/Zgcd_pos.con" as definition.
216 inline procedural "cic:/Coq/ZArith/Znumtheory/Zgcd_spec.con" as definition.
218 inline procedural "cic:/Coq/ZArith/Znumtheory/Zgcd.con" as definition.
220 inline procedural "cic:/Coq/ZArith/Znumtheory/Zgcd_is_pos.con" as lemma.
222 inline procedural "cic:/Coq/ZArith/Znumtheory/Zgcd_is_gcd.con" as lemma.
224 (*#* * Relative primality *)
226 inline procedural "cic:/Coq/ZArith/Znumtheory/rel_prime.con" as definition.
228 (*#* Bezout's theorem: [a] and [b] are relatively prime if and
229 only if there exist [u] and [v] such that [ua+vb = 1]. *)
231 inline procedural "cic:/Coq/ZArith/Znumtheory/rel_prime_bezout.con" as lemma.
233 inline procedural "cic:/Coq/ZArith/Znumtheory/bezout_rel_prime.con" as lemma.
235 (*#* Gauss's theorem: if [a] divides [bc] and if [a] and [b] are
236 relatively prime, then [a] divides [c]. *)
238 inline procedural "cic:/Coq/ZArith/Znumtheory/Gauss.con" as theorem.
240 (*#* If [a] is relatively prime to [b] and [c], then it is to [bc] *)
242 inline procedural "cic:/Coq/ZArith/Znumtheory/rel_prime_mult.con" as lemma.
244 inline procedural "cic:/Coq/ZArith/Znumtheory/rel_prime_cross_prod.con" as lemma.
246 (*#* After factorization by a gcd, the original numbers are relatively prime. *)
248 inline procedural "cic:/Coq/ZArith/Znumtheory/Zis_gcd_rel_prime.con" as lemma.
252 inline procedural "cic:/Coq/ZArith/Znumtheory/prime.ind".
254 (*#* The sole divisors of a prime number [p] are [-1], [1], [p] and [-p]. *)
256 inline procedural "cic:/Coq/ZArith/Znumtheory/prime_divisors.con" as lemma.
258 (*#* A prime number is relatively prime with any number it does not divide *)
260 inline procedural "cic:/Coq/ZArith/Znumtheory/prime_rel_prime.con" as lemma.
263 Hint Resolve prime_rel_prime: zarith.
266 (*#* [Zdivide] can be expressed using [Zmod]. *)
268 inline procedural "cic:/Coq/ZArith/Znumtheory/Zmod_divide.con" as lemma.
270 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_mod.con" as lemma.
272 (*#* [Zdivide] is hence decidable *)
274 inline procedural "cic:/Coq/ZArith/Znumtheory/Zdivide_dec.con" as lemma.
276 (*#* If a prime [p] divides [ab] then it divides either [a] or [b] *)
278 inline procedural "cic:/Coq/ZArith/Znumtheory/prime_mult.con" as lemma.