Remplacement Euclid_def Euclid_proof par Euclid

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@1617 85f007b7-540e-0410-9357-904b9bb8a0f7

1 files changed, 61 insertions, 0 deletions

diff --git a/theories/Arith/Euclid.v b/theories/Arith/Euclid.v
new file mode 100644
index 000000000..c6db2917b
--- /dev/null
+++ b/theories/Arith/Euclid.v
@@ -0,0 +1,61 @@
+(***********************************************************************)
+(*  v      *   The Coq Proof Assistant  /  The Coq Development Team    *)
+(* <O___,, *        INRIA-Rocquencourt  &  LRI-CNRS-Orsay              *)
+(*   \VV/  *************************************************************)
+(*    //   *      This file is distributed under the terms of the      *)
+(*         *       GNU Lesser General Public License Version 2.1       *)
+(***********************************************************************)
+
+(*i $Id$ i*)
+
+Require Mult.
+Require Compare_dec.
+Require Wf_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.
+Save.
+
+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.
+Save.
+
+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.
+Save.