X-Git-Url: http://matita.cs.unibo.it/gitweb/?p=helm.git;a=blobdiff_plain;f=matita%2Fcontribs%2Flibrary_auto%2Fauto%2Fnat%2Fprimes.ma;fp=matita%2Fcontribs%2Flibrary_auto%2Fauto%2Fnat%2Fprimes.ma;h=21d752f71b6fcfe827dbc871723b20b55d4bae09;hp=0000000000000000000000000000000000000000;hb=f61af501fb4608cc4fb062a0864c774e677f0d76;hpb=58ae1809c352e71e7b5530dc41e2bfc834e1aef1

diff --git a/matita/contribs/library_auto/auto/nat/primes.ma b/matita/contribs/library_auto/auto/nat/primes.ma
new file mode 100644
index 000000000..21d752f71
--- /dev/null
+++ b/matita/contribs/library_auto/auto/nat/primes.ma
@@ -0,0 +1,999 @@
+(**************************************************************************)
+(*       ___	                                                            *)
+(*      ||M||                                                             *)
+(*      ||A||       A project by Andrea Asperti                           *)
+(*      ||T||                                                             *)
+(*      ||I||       Developers:                                           *)
+(*      ||T||       A.Asperti, C.Sacerdoti Coen,                          *)
+(*      ||A||       E.Tassi, S.Zacchiroli                                 *)
+(*      \   /                                                             *)
+(*       \ /        Matita is distributed under the terms of the          *)
+(*        v         GNU Lesser General Public License Version 2.1         *)
+(*                                                                        *)
+(**************************************************************************)
+
+set "baseuri" "cic:/matita/library_autobatch/nat/primes".
+
+include "auto/nat/div_and_mod.ma".
+include "auto/nat/minimization.ma".
+include "auto/nat/sigma_and_pi.ma".
+include "auto/nat/factorial.ma".
+
+inductive divides (n,m:nat) : Prop \def
+witness : \forall p:nat.m = times n p \to divides n m.
+
+interpretation "divides" 'divides n m = (cic:/matita/library_autobatch/nat/primes/divides.ind#xpointer(1/1) n m).
+interpretation "not divides" 'ndivides n m =
+ (cic:/matita/logic/connectives/Not.con (cic:/matita/library_autobatch/nat/primes/divides.ind#xpointer(1/1) n m)).
+
+theorem reflexive_divides : reflexive nat divides.
+unfold reflexive.
+intros.
+exact (witness x x (S O) (times_n_SO x)).
+qed.
+
+theorem divides_to_div_mod_spec :
+\forall n,m. O < n \to n \divides m \to div_mod_spec m n (m / n) O.
+intros.
+elim H1.
+rewrite > H2.
+constructor 1
+[ assumption
+| apply (lt_O_n_elim n H).
+  intros.
+  autobatch
+  (*rewrite < plus_n_O.
+  rewrite > div_times.
+  apply sym_times*)
+]
+qed.
+
+theorem div_mod_spec_to_divides :
+\forall n,m,p. div_mod_spec m n p O \to n \divides m.
+intros.
+elim H.
+autobatch.
+(*apply (witness n m p).
+rewrite < sym_times.
+rewrite > (plus_n_O (p*n)).
+assumption*)
+qed.
+
+theorem divides_to_mod_O:
+\forall n,m. O < n \to n \divides m \to (m \mod n) = O.
+intros.
+apply (div_mod_spec_to_eq2 m n (m / n) (m \mod n) (m / n) O)
+[ autobatch
+  (*apply div_mod_spec_div_mod.
+  assumption*)
+| autobatch
+  (*apply divides_to_div_mod_spec;assumption*)
+]
+qed.
+
+theorem mod_O_to_divides:
+\forall n,m. O< n \to (m \mod n) = O \to  n \divides m.
+intros.
+apply (witness n m (m / n)).
+rewrite > (plus_n_O (n * (m / n))).
+rewrite < H1.
+rewrite < sym_times.
+autobatch.
+(* Andrea: perche' hint non lo trova ?*)
+(*apply div_mod.
+assumption.*)
+qed.
+
+theorem divides_n_O: \forall n:nat. n \divides O.
+intro.
+autobatch.
+(*apply (witness n O O).
+apply times_n_O.*)
+qed.
+
+theorem divides_n_n: \forall n:nat. n \divides n.
+autobatch.
+(*intro.
+apply (witness n n (S O)).
+apply times_n_SO.*)
+qed.
+
+theorem divides_SO_n: \forall n:nat. (S O) \divides n.
+intro.
+autobatch.
+(*apply (witness (S O) n n).
+simplify.
+apply plus_n_O.*)
+qed.
+
+theorem divides_plus: \forall n,p,q:nat. 
+n \divides p \to n \divides q \to n \divides p+q.
+intros.
+elim H.
+elim H1.
+apply (witness n (p+q) (n2+n1)).
+autobatch.
+(*rewrite > H2.
+rewrite > H3.
+apply sym_eq.
+apply distr_times_plus.*)
+qed.
+
+theorem divides_minus: \forall n,p,q:nat. 
+divides n p \to divides n q \to divides n (p-q).
+intros.
+elim H.
+elim H1.
+apply (witness n (p-q) (n2-n1)).
+autobatch.
+(*rewrite > H2.
+rewrite > H3.
+apply sym_eq.
+apply distr_times_minus.*)
+qed.
+
+theorem divides_times: \forall n,m,p,q:nat. 
+n \divides p \to m \divides q \to n*m \divides p*q.
+intros.
+elim H.
+elim H1.
+apply (witness (n*m) (p*q) (n2*n1)).
+rewrite > H2.
+rewrite > H3.
+apply (trans_eq nat ? (n*(m*(n2*n1))))
+[ apply (trans_eq nat ? (n*(n2*(m*n1))))
+  [ apply assoc_times
+  | apply eq_f.
+    apply (trans_eq nat ? ((n2*m)*n1))
+    [ autobatch
+      (*apply sym_eq. 
+      apply assoc_times*)
+    | rewrite > (sym_times n2 m).
+      apply assoc_times
+    ]
+  ]
+| autobatch
+  (*apply sym_eq. 
+  apply assoc_times*)
+]
+qed.
+
+theorem transitive_divides: transitive ? divides.
+unfold.
+intros.
+elim H.
+elim H1.
+apply (witness x z (n2*n)).
+autobatch.
+(*rewrite > H3.
+rewrite > H2.
+apply assoc_times.*)
+qed.
+
+variant trans_divides: \forall n,m,p. 
+ n \divides m \to m \divides p \to n \divides p \def transitive_divides.
+
+theorem eq_mod_to_divides:\forall n,m,p. O< p \to
+mod n p = mod m p \to divides p (n-m).
+intros.
+cut (n \le m \or \not n \le m)
+[ elim Hcut
+  [ cut (n-m=O)
+    [ autobatch
+      (*rewrite > Hcut1.
+      apply (witness p O O).
+      apply times_n_O*)
+    | autobatch
+      (*apply eq_minus_n_m_O.
+      assumption*)
+    ]
+  | apply (witness p (n-m) ((div n p)-(div m p))).
+    rewrite > distr_times_minus.
+    rewrite > sym_times.
+    rewrite > (sym_times p).
+    cut ((div n p)*p = n - (mod n p))
+    [ rewrite > Hcut1.
+      rewrite > eq_minus_minus_minus_plus.
+      rewrite > sym_plus.
+      rewrite > H1.
+      autobatch
+      (*rewrite < div_mod
+      [ reflexivity
+      | assumption
+      ]*)
+    | apply sym_eq.
+      apply plus_to_minus.
+      rewrite > sym_plus.
+      autobatch
+      (*apply div_mod.
+      assumption*)
+    ]
+  ]
+| apply (decidable_le n m)
+]
+qed.
+
+theorem antisymmetric_divides: antisymmetric nat divides.
+unfold antisymmetric.
+intros.
+elim H.
+elim H1.
+apply (nat_case1 n2)
+[ intro.
+  rewrite > H3.
+  rewrite > H2.
+  rewrite > H4.  
+  rewrite < times_n_O.
+  reflexivity
+| intros.
+  apply (nat_case1 n)
+  [ intro.
+    rewrite > H2.
+    rewrite > H3.
+    rewrite > H5.
+    autobatch
+    (*rewrite < times_n_O.
+    reflexivity*)
+  | intros.
+    apply antisymmetric_le
+    [ rewrite > H2.
+      rewrite > times_n_SO in \vdash (? % ?).
+      apply le_times_r.
+      rewrite > H4.
+      autobatch
+      (*apply le_S_S.
+      apply le_O_n*)
+    | rewrite > H3.
+      rewrite > times_n_SO in \vdash (? % ?).
+      apply le_times_r.
+      rewrite > H5.
+      autobatch
+      (*apply le_S_S.
+      apply le_O_n*)
+    ]
+  ]
+]
+qed.
+
+(* divides le *)
+theorem divides_to_le : \forall n,m. O < m \to n \divides m \to n \le m.
+intros.
+elim H1.
+rewrite > H2.
+cut (O < n2)
+[ apply (lt_O_n_elim n2 Hcut).
+  intro.
+  autobatch
+  (*rewrite < sym_times.
+  simplify.
+  rewrite < sym_plus.
+  apply le_plus_n*)
+| elim (le_to_or_lt_eq O n2)
+  [ assumption
+  | absurd (O<m)
+    [ assumption
+    | rewrite > H2.
+      rewrite < H3.
+      rewrite < times_n_O.
+      apply (not_le_Sn_n O)
+    ]
+  | apply le_O_n
+  ]
+]
+qed.
+
+theorem divides_to_lt_O : \forall n,m. O < m \to n \divides m \to O < n.
+intros.
+elim H1.
+elim (le_to_or_lt_eq O n (le_O_n n))
+[ assumption
+| rewrite < H3.
+  absurd (O < m)
+  [ assumption
+  | rewrite > H2.
+    rewrite < H3.
+    autobatch
+    (*simplify.
+    exact (not_le_Sn_n O)*)
+  ]
+]
+qed.
+
+(* boolean divides *)
+definition divides_b : nat \to nat \to bool \def
+\lambda n,m :nat. (eqb (m \mod n) O).
+  
+theorem divides_b_to_Prop :
+\forall n,m:nat. O < n \to
+match divides_b n m with
+[ true \Rightarrow n \divides m
+| false \Rightarrow n \ndivides m].
+intros.
+unfold divides_b.
+apply eqb_elim
+[ intro.
+  simplify.
+  autobatch
+  (*apply mod_O_to_divides;assumption*)
+| intro.
+  simplify.
+  unfold Not.
+  intro.
+  autobatch
+  (*apply H1.
+  apply divides_to_mod_O;assumption*)
+]
+qed.
+
+theorem divides_b_true_to_divides :
+\forall n,m:nat. O < n \to
+(divides_b n m = true ) \to n \divides m.
+intros.
+change with 
+match true with
+[ true \Rightarrow n \divides m
+| false \Rightarrow n \ndivides m].
+rewrite < H1.
+apply divides_b_to_Prop.
+assumption.
+qed.
+
+theorem divides_b_false_to_not_divides :
+\forall n,m:nat. O < n \to
+(divides_b n m = false ) \to n \ndivides m.
+intros.
+change with 
+match false with
+[ true \Rightarrow n \divides m
+| false \Rightarrow n \ndivides m].
+rewrite < H1.
+apply divides_b_to_Prop.
+assumption.
+qed.
+
+theorem decidable_divides: \forall n,m:nat.O < n \to
+decidable (n \divides m).
+intros.
+unfold decidable.
+cut 
+(match divides_b n m with
+[ true \Rightarrow n \divides m
+| false \Rightarrow n \ndivides m] \to n \divides m \lor n \ndivides m)
+[ apply Hcut.
+  apply divides_b_to_Prop.
+  assumption
+| elim (divides_b n m)
+  [ left.
+    (*qui autobatch non chiude il goal, chiuso dalla sola apply H1*)
+    apply H1
+  | right.
+    (*qui autobatch non chiude il goal, chiuso dalla sola apply H1*)
+    apply H1
+  ]
+]
+qed.
+
+theorem divides_to_divides_b_true : \forall n,m:nat. O < n \to
+n \divides m \to divides_b n m = true.
+intros.
+cut (match (divides_b n m) with
+[ true \Rightarrow n \divides m
+| false \Rightarrow n \ndivides m] \to ((divides_b n m) = true))
+[ apply Hcut.
+  apply divides_b_to_Prop.
+  assumption
+| elim (divides_b n m)
+  [ reflexivity
+  | absurd (n \divides m)
+    [ assumption
+    | (*qui autobatch non chiude il goal, chiuso dalla sola applicazione di assumption*)
+      assumption
+    ]
+  ]
+]
+qed.
+
+theorem not_divides_to_divides_b_false: \forall n,m:nat. O < n \to
+\lnot(n \divides m) \to (divides_b n m) = false.
+intros.
+cut (match (divides_b n m) with
+[ true \Rightarrow n \divides m
+| false \Rightarrow n \ndivides m] \to ((divides_b n m) = false))
+[ apply Hcut.
+  apply divides_b_to_Prop.
+  assumption
+| elim (divides_b n m)
+  [ absurd (n \divides m)
+    [ (*qui autobatch non chiude il goal, chiuso dalla sola tattica assumption*)
+      assumption
+    | assumption
+    ]
+  | reflexivity
+  ]
+]
+qed.
+
+(* divides and pi *)
+theorem divides_f_pi_f : \forall f:nat \to nat.\forall n,m,i:nat. 
+m \le i \to i \le n+m \to f i \divides pi n f m.
+intros 5.
+elim n
+[ simplify.
+  cut (i = m)
+  [ autobatch
+    (*rewrite < Hcut.
+    apply divides_n_n*)
+  | apply antisymmetric_le
+    [ assumption
+    | assumption
+    ]
+  ]
+| simplify.
+  cut (i < S n1+m \lor i = S n1 + m)
+  [ elim Hcut
+    [ apply (transitive_divides ? (pi n1 f m))
+      [ apply H1.
+        autobatch
+        (*apply le_S_S_to_le.
+        assumption*)
+      | autobatch
+        (*apply (witness ? ? (f (S n1+m))).
+        apply sym_times*)
+      ]
+    | autobatch
+      (*rewrite > H3.
+      apply (witness ? ? (pi n1 f m)).
+      reflexivity*)
+    ]
+  | autobatch
+    (*apply le_to_or_lt_eq.
+    assumption*)
+  ]
+]
+qed.
+
+(*
+theorem mod_S_pi: \forall f:nat \to nat.\forall n,i:nat. 
+i < n \to (S O) < (f i) \to (S (pi n f)) \mod (f i) = (S O).
+intros.cut (pi n f) \mod (f i) = O.
+rewrite < Hcut.
+apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
+rewrite > Hcut.assumption.
+apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
+apply divides_f_pi_f.assumption.
+qed.
+*)
+
+(* divides and fact *)
+theorem divides_fact : \forall n,i:nat. 
+O < i \to i \le n \to i \divides n!.
+intros 3.
+elim n
+[ absurd (O<i)
+  [ assumption
+  | autobatch
+    (*apply (le_n_O_elim i H1).
+    apply (not_le_Sn_O O)*)
+  ]
+| change with (i \divides (S n1)*n1!).
+  apply (le_n_Sm_elim i n1 H2)
+  [ intro.
+    apply (transitive_divides ? n1!)
+    [ autobatch
+      (*apply H1.
+      apply le_S_S_to_le. 
+      assumption*)
+    | autobatch
+      (*apply (witness ? ? (S n1)).
+      apply sym_times*)
+    ]
+  | intro.
+    autobatch
+    (*rewrite > H3.
+    apply (witness ? ? n1!).
+    reflexivity*)
+  ]
+]
+qed.
+
+theorem mod_S_fact: \forall n,i:nat. 
+(S O) < i \to i \le n \to (S n!) \mod i = (S O).
+intros.
+cut (n! \mod i = O)
+[ rewrite < Hcut.
+  apply mod_S
+  [ autobatch
+    (*apply (trans_lt O (S O))
+    [ apply (le_n (S O))
+    | assumption
+    ]*)
+  | rewrite > Hcut.
+    assumption
+  ]
+| autobatch(*
+  apply divides_to_mod_O
+  [ apply ltn_to_ltO [| apply H]
+  | apply divides_fact
+    [ apply ltn_to_ltO [| apply H]
+    | assumption
+    ]
+  ]*)
+] 
+qed.
+
+theorem not_divides_S_fact: \forall n,i:nat. 
+(S O) < i \to i \le n \to i \ndivides S n!.
+intros.
+apply divides_b_false_to_not_divides
+[ autobatch
+  (*apply (trans_lt O (S O))
+  [ apply (le_n (S O))
+  | assumption
+  ]*)
+| unfold divides_b.
+  rewrite > mod_S_fact;autobatch
+  (*[ simplify.
+    reflexivity
+  | assumption
+  | assumption
+  ]*)
+]
+qed.
+
+(* prime *)
+definition prime : nat \to  Prop \def
+\lambda n:nat. (S O) < n \land 
+(\forall m:nat. m \divides n \to (S O) < m \to  m = n).
+
+theorem not_prime_O: \lnot (prime O).
+unfold Not.
+unfold prime.
+intro.
+elim H.
+apply (not_le_Sn_O (S O) H1).
+qed.
+
+theorem not_prime_SO: \lnot (prime (S O)).
+unfold Not.
+unfold prime.
+intro.
+elim H.
+apply (not_le_Sn_n (S O) H1).
+qed.
+
+(* smallest factor *)
+definition smallest_factor : nat \to nat \def
+\lambda n:nat. 
+match n with
+[ O \Rightarrow O
+| (S p) \Rightarrow 
+  match p with
+  [ O \Rightarrow (S O)
+  | (S q) \Rightarrow min_aux q (S(S q)) (\lambda m.(eqb ((S(S q)) \mod m) O))]].
+
+(* it works ! 
+theorem example1 : smallest_prime_factor (S(S(S O))) = (S(S(S O))).
+normalize.reflexivity.
+qed.
+
+theorem example2: smallest_prime_factor (S(S(S(S O)))) = (S(S O)).
+normalize.reflexivity.
+qed.
+
+theorem example3 : smallest_prime_factor (S(S(S(S(S(S(S O))))))) = (S(S(S(S(S(S(S O))))))).
+simplify.reflexivity.
+qed. *)
+
+theorem lt_SO_smallest_factor: 
+\forall n:nat. (S O) < n \to (S O) < (smallest_factor n).
+intro.
+apply (nat_case n)
+[ autobatch
+  (*intro.
+  apply False_ind.
+  apply (not_le_Sn_O (S O) H)*)
+| intro.
+  apply (nat_case m)
+  [ autobatch
+    (*intro. apply False_ind.
+    apply (not_le_Sn_n (S O) H)*)  
+  | intros.
+    change with 
+    (S O < min_aux m1 (S(S m1)) (\lambda m.(eqb ((S(S m1)) \mod m) O))).
+    apply (lt_to_le_to_lt ? (S (S O)))
+    [ apply (le_n (S(S O)))
+    | cut ((S(S O)) = (S(S m1)) - m1)
+      [ rewrite > Hcut.
+        apply le_min_aux
+      | apply sym_eq.
+        apply plus_to_minus.
+        autobatch
+        (*rewrite < sym_plus.
+        simplify.
+        reflexivity*)        
+      ]
+    ]
+  ]
+]
+qed.
+
+theorem lt_O_smallest_factor: \forall n:nat. O < n \to O < (smallest_factor n).
+intro.
+apply (nat_case n)
+[ autobatch
+  (*intro.
+  apply False_ind.
+  apply (not_le_Sn_n O H)*)
+| intro.
+  apply (nat_case m)
+  [ autobatch
+    (*intro.
+    simplify.
+    unfold lt.
+    apply le_n*)
+  | intros.
+    apply (trans_lt ? (S O))
+    [ autobatch
+      (*unfold lt.
+      apply le_n*)
+    | apply lt_SO_smallest_factor.
+      unfold lt.autobatch
+      (*apply le_S_S.
+      apply le_S_S.
+      apply le_O_n*)     
+    ]
+  ]
+]
+qed.
+
+theorem divides_smallest_factor_n : 
+\forall n:nat. O < n \to smallest_factor n \divides n.
+intro.
+apply (nat_case n)
+[ intro.
+  autobatch
+  (*apply False_ind.
+  apply (not_le_Sn_O O H)*)
+| intro.
+  apply (nat_case m)
+  [ intro.
+    autobatch
+    (*simplify.
+    apply (witness ? ? (S O)). 
+    simplify.
+    reflexivity*)
+  | intros.
+    apply divides_b_true_to_divides
+    [ apply (lt_O_smallest_factor ? H)
+    | change with 
+       (eqb ((S(S m1)) \mod (min_aux m1 (S(S m1)) 
+       (\lambda m.(eqb ((S(S m1)) \mod m) O)))) O = true).
+      apply f_min_aux_true.
+      apply (ex_intro nat ? (S(S m1))).
+      split
+      [ autobatch
+        (*split
+        [ apply le_minus_m
+        | apply le_n
+        ]*)
+      | autobatch
+        (*rewrite > mod_n_n
+        [ reflexivity
+        | apply (trans_lt ? (S O))
+          [ apply (le_n (S O))
+          | unfold lt.
+            apply le_S_S.
+            apply le_S_S.
+            apply le_O_n
+          ]
+        ]*)
+      ]
+    ]
+  ]
+]
+qed.
+  
+theorem le_smallest_factor_n : 
+\forall n:nat. smallest_factor n \le n.
+intro.
+apply (nat_case n)
+[ autobatch
+  (*simplify.
+  apply le_n*)
+| intro.
+  autobatch
+  (*apply (nat_case m)
+  [ simplify.
+    apply le_n
+  | intro.
+    apply divides_to_le
+    [ unfold lt.
+      apply le_S_S.
+      apply le_O_n
+    | apply divides_smallest_factor_n.
+      unfold lt.
+      apply le_S_S.
+      apply le_O_n
+    ]
+  ]*)
+]
+qed.
+
+theorem lt_smallest_factor_to_not_divides: \forall n,i:nat. 
+(S O) < n \to (S O) < i \to i < (smallest_factor n) \to i \ndivides n.
+intros 2.
+apply (nat_case n)
+[ intro.
+  apply False_ind.
+  apply (not_le_Sn_O (S O) H)
+| intro.
+  apply (nat_case m)
+  [ intro.
+    apply False_ind.
+    apply (not_le_Sn_n (S O) H)
+  | intros.
+    apply divides_b_false_to_not_divides
+    [ autobatch
+      (*apply (trans_lt O (S O))
+      [ apply (le_n (S O))
+      | assumption
+      ]*)
+    | unfold divides_b.
+      apply (lt_min_aux_to_false 
+      (\lambda i:nat.eqb ((S(S m1)) \mod i) O) (S(S m1)) m1 i)
+      [ cut ((S(S O)) = (S(S m1)-m1))
+        [ rewrite < Hcut.
+          exact H1
+        | apply sym_eq.        
+          apply plus_to_minus.
+          autobatch
+          (*rewrite < sym_plus.
+          simplify.
+          reflexivity*)
+        ]
+      | exact H2
+      ]
+    ]
+  ]
+]
+qed.
+
+theorem prime_smallest_factor_n : 
+\forall n:nat. (S O) < n \to prime (smallest_factor n).
+intro.
+change with ((S(S O)) \le n \to (S O) < (smallest_factor n) \land 
+(\forall m:nat. m \divides smallest_factor n \to (S O) < m \to  m = (smallest_factor n))).
+intro.
+split
+[ apply lt_SO_smallest_factor.
+  assumption
+| intros.
+  cut (le m (smallest_factor n))
+  [ elim (le_to_or_lt_eq m (smallest_factor n) Hcut)
+    [ absurd (m \divides n)
+      [ apply (transitive_divides m (smallest_factor n))
+        [ assumption
+        | apply divides_smallest_factor_n.
+          autobatch
+          (*apply (trans_lt ? (S O))
+          [ unfold lt. 
+            apply le_n
+          | exact H
+          ]*)
+        ]
+      | apply lt_smallest_factor_to_not_divides;autobatch      
+        (*[ exact H
+        | assumption
+        | assumption
+        ]*)
+      ]
+    | assumption
+    ]
+  | apply divides_to_le
+    [ apply (trans_lt O (S O))
+      [ apply (le_n (S O))
+      | apply lt_SO_smallest_factor.      
+        exact H
+      ]
+    | assumption
+    ]
+  ]
+]
+qed.
+
+theorem prime_to_smallest_factor: \forall n. prime n \to
+smallest_factor n = n.
+intro.
+apply (nat_case n)
+[ intro.
+  autobatch
+  (*apply False_ind.
+  apply (not_prime_O H)*)
+| intro.
+  apply (nat_case m)
+  [ intro.
+    autobatch
+    (*apply False_ind.
+    apply (not_prime_SO H)*)
+  | intro.
+    change with 
+     ((S O) < (S(S m1)) \land 
+     (\forall m:nat. m \divides S(S m1) \to (S O) < m \to  m = (S(S m1))) \to 
+    smallest_factor (S(S m1)) = (S(S m1))).
+    intro.
+    elim H.
+    autobatch
+    (*apply H2
+    [ apply divides_smallest_factor_n.
+      apply (trans_lt ? (S O))
+      [ unfold lt. 
+        apply le_n
+      | assumption
+      ]
+    | apply lt_SO_smallest_factor.
+      assumption
+    ]*)
+  ]
+]
+qed.
+
+(* a number n > O is prime iff its smallest factor is n *)
+definition primeb \def \lambda n:nat.
+match n with
+[ O \Rightarrow false
+| (S p) \Rightarrow
+  match p with
+  [ O \Rightarrow false
+  | (S q) \Rightarrow eqb (smallest_factor (S(S q))) (S(S q))]].
+
+(* it works! 
+theorem example4 : primeb (S(S(S O))) = true.
+normalize.reflexivity.
+qed.
+
+theorem example5 : primeb (S(S(S(S(S(S O)))))) = false.
+normalize.reflexivity.
+qed.
+
+theorem example6 : primeb (S(S(S(S((S(S(S(S(S(S(S O)))))))))))) = true.
+normalize.reflexivity.
+qed.
+
+theorem example7 : primeb (S(S(S(S(S(S((S(S(S(S((S(S(S(S(S(S(S O))))))))))))))))))) = true.
+normalize.reflexivity.
+qed. *)
+
+theorem primeb_to_Prop: \forall n.
+match primeb n with
+[ true \Rightarrow prime n
+| false \Rightarrow \lnot (prime n)].
+intro.
+apply (nat_case n)
+[ simplify.
+  autobatch
+  (*unfold Not.
+  unfold prime.
+  intro.
+  elim H.
+  apply (not_le_Sn_O (S O) H1)*)
+| intro.
+  apply (nat_case m)
+  [ simplify.
+    autobatch
+    (*unfold Not.
+    unfold prime.
+    intro.
+    elim H.
+    apply (not_le_Sn_n (S O) H1)*)
+  | intro.
+    change with 
+    match eqb (smallest_factor (S(S m1))) (S(S m1)) with
+    [ true \Rightarrow prime (S(S m1))
+    | false \Rightarrow \lnot (prime (S(S m1)))].
+    apply (eqb_elim (smallest_factor (S(S m1))) (S(S m1)))
+    [ intro.
+      simplify.
+      rewrite < H.
+      apply prime_smallest_factor_n.
+      unfold lt.autobatch
+      (*apply le_S_S.
+      apply le_S_S.
+      apply le_O_n*)
+    | intro.
+      simplify.
+      change with (prime (S(S m1)) \to False).
+      intro.
+      autobatch      
+      (*apply H.
+      apply prime_to_smallest_factor.
+      assumption*)
+    ]
+  ]
+]
+qed.
+
+theorem primeb_true_to_prime : \forall n:nat.
+primeb n = true \to prime n.
+intros.
+change with
+match true with 
+[ true \Rightarrow prime n
+| false \Rightarrow \lnot (prime n)].
+rewrite < H.
+(*qui autobatch non chiude il goal*)
+apply primeb_to_Prop.
+qed.
+
+theorem primeb_false_to_not_prime : \forall n:nat.
+primeb n = false \to \lnot (prime n).
+intros.
+change with
+match false with 
+[ true \Rightarrow prime n
+| false \Rightarrow \lnot (prime n)].
+rewrite < H.
+(*qui autobatch non chiude il goal*)
+apply primeb_to_Prop.
+qed.
+
+theorem decidable_prime : \forall n:nat.decidable (prime n).
+intro.
+unfold decidable.
+cut 
+(match primeb n with
+[ true \Rightarrow prime n
+| false \Rightarrow \lnot (prime n)] \to (prime n) \lor \lnot (prime n))
+[ apply Hcut.
+  (*qui autobatch non chiude il goal*)
+  apply primeb_to_Prop
+| elim (primeb n)
+  [ left.
+    (*qui autobatch non chiude il goal*)
+    apply H
+  | right.
+    (*qui autobatch non chiude il goal*)
+    apply H
+  ]
+]
+qed.
+
+theorem prime_to_primeb_true: \forall n:nat. 
+prime n \to primeb n = true.
+intros.
+cut (match (primeb n) with
+[ true \Rightarrow prime n
+| false \Rightarrow \lnot (prime n)] \to ((primeb n) = true))
+[ apply Hcut.
+  (*qui autobatch non chiude il goal*)
+  apply primeb_to_Prop
+| elim (primeb n)
+  [ reflexivity.
+  | absurd (prime n)
+    [ assumption
+    | (*qui autobatch non chiude il goal*)
+      assumption
+    ]
+  ]
+]
+qed.
+
+theorem not_prime_to_primeb_false: \forall n:nat. 
+\lnot(prime n) \to primeb n = false.
+intros.
+cut (match (primeb n) with
+[ true \Rightarrow prime n
+| false \Rightarrow \lnot (prime n)] \to ((primeb n) = false))
+[ apply Hcut.
+  (*qui autobatch non chiude il goal*)
+  apply primeb_to_Prop
+| elim (primeb n)
+  [ absurd (prime n)
+    [ (*qui autobatch non chiude il goal*)
+      assumption
+    | assumption
+    ]
+  | reflexivity
+  ]
+]
+qed.
+