blob: adeaf7133f88f9eaaf16af93621e2a838a41c7fa (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
(************************************************************************)
(* v * The Coq Proof Assistant / The Coq Development Team *)
(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
(* \VV/ **************************************************************)
(* // * This file is distributed under the terms of the *)
(* * GNU Lesser General Public License Version 2.1 *)
(************************************************************************)
(*i $Id: Euclid.v,v 1.1.2.1 2004/07/16 19:31:24 herbelin Exp $ i*)
Require Mult.
Require Compare_dec.
Require Wf_nat.
V7only [Import nat_scope.].
Open Local Scope nat_scope.
Implicit Variables Type a,b,n,q,r:nat.
Inductive diveucl [a,b:nat] : Set
:= divex : (q,r:nat)(gt b r)->(a=(plus (mult q b) r))->(diveucl a b).
Lemma eucl_dev : (b:nat)(gt b O)->(a:nat)(diveucl a b).
Intros b H a; Pattern a; Apply gt_wf_rec; Intros n H0.
Elim (le_gt_dec b n).
Intro lebn.
Elim (H0 (minus n b)); Auto with arith.
Intros q r g e.
Apply divex with (S q) r; Simpl; Auto with arith.
Elim plus_assoc_l.
Elim e; Auto with arith.
Intros gtbn.
Apply divex with O n; Simpl; Auto with arith.
Qed.
Lemma quotient : (b:nat)(gt b O)->
(a:nat){q:nat|(EX r:nat | (a=(plus (mult q b) r))/\(gt b r))}.
Intros b H a; Pattern a; Apply gt_wf_rec; Intros n H0.
Elim (le_gt_dec b n).
Intro lebn.
Elim (H0 (minus n b)); Auto with arith.
Intros q Hq; Exists (S q).
Elim Hq; Intros r Hr.
Exists r; Simpl; Elim Hr; Intros.
Elim plus_assoc_l.
Elim H1; Auto with arith.
Intros gtbn.
Exists O; Exists n; Simpl; Auto with arith.
Qed.
Lemma modulo : (b:nat)(gt b O)->
(a:nat){r:nat|(EX q:nat | (a=(plus (mult q b) r))/\(gt b r))}.
Intros b H a; Pattern a; Apply gt_wf_rec; Intros n H0.
Elim (le_gt_dec b n).
Intro lebn.
Elim (H0 (minus n b)); Auto with arith.
Intros r Hr; Exists r.
Elim Hr; Intros q Hq.
Elim Hq; Intros; Exists (S q); Simpl.
Elim plus_assoc_l.
Elim H1; Auto with arith.
Intros gtbn.
Exists n; Exists O; Simpl; Auto with arith.
Qed.
|
