added to applyS in nat/gcd.ma a timeout large enough for compilation in bytecode

[helm.git] / helm / software / matita / library / nat / gcd.ma

diff --git a/helm/software/matita/library/nat/gcd.ma b/helm/software/matita/library/nat/gcd.ma
index 65f61b581691cdabbdaeeb34fc7d10ac21927a93..fdb1e8d9018dc5b877c52e93918894a6c43194f5 100644 (file)
--- a/helm/software/matita/library/nat/gcd.ma
+++ b/helm/software/matita/library/nat/gcd.ma
@@ -67,21 +67,13 @@ gcd_aux p m n \divides m \land gcd_aux p m n \divides n.
 intro.elim p.
 absurd (O < n).assumption.apply le_to_not_lt.assumption.
 cut ((n1 \divides m) \lor (n1 \ndivides m)).
-change with 
-((match divides_b n1 m with
-[ true \Rightarrow n1
-| false \Rightarrow gcd_aux n n1 (m \mod n1)]) \divides m \land
-(match divides_b n1 m with
-[ true \Rightarrow n1
-| false \Rightarrow gcd_aux n n1 (m \mod n1)]) \divides n1).
+simplify.
 elim Hcut.rewrite > divides_to_divides_b_true.
 simplify.
 split.assumption.apply (witness n1 n1 (S O)).apply times_n_SO.
 assumption.assumption.
 rewrite > not_divides_to_divides_b_false.
-change with 
-(gcd_aux n n1 (m \mod n1) \divides m \land
-gcd_aux n n1 (m \mod n1) \divides n1).
+simplify.
 cut (gcd_aux n n1 (m \mod n1) \divides n1 \land
 gcd_aux n n1 (m \mod n1) \divides mod m n1).
 elim Hcut1.
@@ -106,6 +98,7 @@ qed.
 theorem divides_gcd_nm: \forall n,m.
 gcd n m \divides m \land gcd n m \divides n.
 intros.
+(*CSC: simplify simplifies too much because of a redex in gcd *)
 change with
 (match leb n m with
   [ true \Rightarrow 
@@ -172,18 +165,14 @@ theorem divides_gcd_aux: \forall p,m,n,d. O < n \to n \le m \to n \le p \to
 d \divides m \to d \divides n \to d \divides gcd_aux p m n. 
 intro.elim p.
 absurd (O < n).assumption.apply le_to_not_lt.assumption.
-change with
-(d \divides
-(match divides_b n1 m with
-[ true \Rightarrow n1
-| false \Rightarrow gcd_aux n n1 (m \mod n1)])).
+simplify.
 cut (n1 \divides m \lor n1 \ndivides m).
 elim Hcut.
 rewrite > divides_to_divides_b_true.
 simplify.assumption.
 assumption.assumption.
 rewrite > not_divides_to_divides_b_false.
-change with (d \divides gcd_aux n n1 (m \mod n1)).
+simplify.
 apply H.
 cut (O \lt m \mod n1 \lor O = m \mod n1).
 elim Hcut1.assumption.
@@ -205,6 +194,7 @@ qed.
 theorem divides_d_gcd: \forall m,n,d. 
 d \divides m \to d \divides n \to d \divides gcd n m. 
 intros.
+(*CSC: here simplify simplifies too much because of a redex in gcd *)
 change with
 (d \divides
 match leb n m with
@@ -239,15 +229,7 @@ elim p.
 absurd (O < n).assumption.apply le_to_not_lt.assumption.
 cut (O < m).
 cut (n1 \divides m \lor  n1 \ndivides m).
-change with
-(\exists a,b.
-a*n1 - b*m = match divides_b n1 m with
-[ true \Rightarrow n1
-| false \Rightarrow gcd_aux n n1 (m \mod n1)]
-\lor 
-b*m - a*n1 = match divides_b n1 m with
-[ true \Rightarrow n1
-| false \Rightarrow gcd_aux n n1 (m \mod n1)]).
+simplify.
 elim Hcut1.
 rewrite > divides_to_divides_b_true.
 simplify.
@@ -401,6 +383,7 @@ intros.unfold lt.apply le_S_S.apply le_O_n.
 qed.
 
 theorem symmetric_gcd: symmetric nat gcd.
+(*CSC: bug here: unfold symmetric does not work *)
 change with 
 (\forall n,m:nat. gcd n m = gcd m n).
 intros.
@@ -430,7 +413,7 @@ symmetric_gcd.
 
 theorem le_gcd_times: \forall m,n,p:nat. O< p \to gcd m n \le gcd m (n*p).
 intros.
-apply (nat_case n).reflexivity.
+apply (nat_case n).apply le_n.
 intro.
 apply divides_to_le.
 apply lt_O_gcd.
@@ -502,11 +485,11 @@ qed.
 
 theorem prime_to_gcd_SO: \forall n,m:nat. prime n \to n \ndivides m \to
 gcd n m = (S O).
-intros.unfold prime in H.change with (gcd n m = (S O)). 
+intros.unfold prime in H.
 elim H.
 apply antisym_le.
-apply not_lt_to_le.
-change with ((S (S O)) \le gcd n m \to False).intro.
+apply not_lt_to_le.unfold Not.unfold lt.
+intro.
 apply H1.rewrite < (H3 (gcd n m)).
 apply divides_gcd_m.
 apply divides_gcd_n.assumption.
@@ -523,42 +506,52 @@ qed.
 theorem divides_times_to_divides: \forall n,p,q:nat.prime n \to n \divides p*q \to
 n \divides p \lor n \divides q.
 intros.
-cut (n \divides p \lor n \ndivides p).
-elim Hcut.
-left.assumption.
-right.
-cut (\exists a,b. a*n - b*p = (S O) \lor b*p - a*n = (S O)).
-elim Hcut1.elim H3.elim H4.
-(* first case *)
-rewrite > (times_n_SO q).rewrite < H5.
-rewrite > distr_times_minus.
-rewrite > (sym_times q (a1*p)).
-rewrite > (assoc_times a1).
-elim H1.rewrite > H6.
-rewrite < (sym_times n).rewrite < assoc_times.
-rewrite > (sym_times q).rewrite > assoc_times.
-rewrite < (assoc_times a1).rewrite < (sym_times n).
-rewrite > (assoc_times n).
-rewrite < distr_times_minus.
-apply (witness ? ? (q*a-a1*n2)).reflexivity.
-(* second case *)
-rewrite > (times_n_SO q).rewrite < H5.
-rewrite > distr_times_minus.
-rewrite > (sym_times q (a1*p)).
-rewrite > (assoc_times a1).
-elim H1.rewrite > H6.
-rewrite < sym_times.rewrite > assoc_times.
-rewrite < (assoc_times q).
-rewrite < (sym_times n).
-rewrite < distr_times_minus.
-apply (witness ? ? (n2*a1-q*a)).reflexivity.
-(* end second case *)
-rewrite < (prime_to_gcd_SO n p).
-apply eq_minus_gcd.
-assumption.assumption.
-apply (decidable_divides n p).
-apply (trans_lt ? (S O)).unfold lt.apply le_n.
-unfold prime in H.elim H. assumption.
+cut (n \divides p \lor n \ndivides p)
+  [elim Hcut
+    [left.assumption
+    |right.
+     cut (\exists a,b. a*n - b*p = (S O) \lor b*p - a*n = (S O))
+       [elim Hcut1.elim H3.elim H4
+         [(* first case *)
+          rewrite > (times_n_SO q).rewrite < H5.
+          rewrite > distr_times_minus.
+          rewrite > (sym_times q (a1*p)).
+          rewrite > (assoc_times a1).
+          elim H1.rewrite > H6.
+          (* applyS (witness n (n*(q*a-a1*n2)) (q*a-a1*n2))
+             reflexivity. *);
+          applyS (witness n ? ? (refl_eq ? ?)) timeout=50.
+          (*
+          rewrite < (sym_times n).rewrite < assoc_times.
+          rewrite > (sym_times q).rewrite > assoc_times.
+          rewrite < (assoc_times a1).rewrite < (sym_times n).
+          rewrite > (assoc_times n).
+          rewrite < distr_times_minus.
+          apply (witness ? ? (q*a-a1*n2)).reflexivity
+          *)
+         |(* second case *)
+          rewrite > (times_n_SO q).rewrite < H5.
+          rewrite > distr_times_minus.
+          rewrite > (sym_times q (a1*p)).
+          rewrite > (assoc_times a1).
+          elim H1.rewrite > H6.
+          rewrite < sym_times.rewrite > assoc_times.
+          rewrite < (assoc_times q).
+          rewrite < (sym_times n).
+          rewrite < distr_times_minus.
+          apply (witness ? ? (n2*a1-q*a)).reflexivity
+        ](* end second case *)
+     |rewrite < (prime_to_gcd_SO n p)
+       [apply eq_minus_gcd|assumption|assumption
+       ]
+     ]
+   ]
+ |apply (decidable_divides n p).
+  apply (trans_lt ? (S O))
+    [unfold lt.apply le_n
+    |unfold prime in H.elim H. assumption
+    ]
+  ]
 qed.
 
 theorem eq_gcd_times_SO: \forall m,n,p:nat. O < n \to O < p \to