1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| A.Asperti, C.Sacerdoti Coen, *)
8 (* ||A|| E.Tassi, S.Zacchiroli *)
10 (* \ / Matita is distributed under the terms of the *)
11 (* v GNU Lesser General Public License Version 2.1 *)
13 (**************************************************************************)
15 set "baseuri" "cic:/matita/nat/primes".
17 include "nat/div_and_mod.ma".
18 include "nat/minimization.ma".
19 include "nat/sigma_and_pi.ma".
20 include "nat/factorial.ma".
22 inductive divides (n,m:nat) : Prop \def
23 witness : \forall p:nat.m = times n p \to divides n m.
25 theorem reflexive_divides : reflexive nat divides.
28 exact witness x x (S O) (times_n_SO x).
31 theorem divides_to_div_mod_spec :
32 \forall n,m. O < n \to divides n m \to div_mod_spec m n (div m n) O.
33 intros.elim H1.rewrite > H2.
34 constructor 1.assumption.
35 apply lt_O_n_elim n H.intros.
37 rewrite > div_times.apply sym_times.
40 theorem div_mod_spec_to_div :
41 \forall n,m,p. div_mod_spec m n p O \to divides n m.
45 rewrite > plus_n_O (p*n).assumption.
48 theorem divides_to_mod_O:
49 \forall n,m. O < n \to divides n m \to (mod m n) = O.
50 intros.apply div_mod_spec_to_eq2 m n (div m n) (mod m n) (div m n) O.
51 apply div_mod_spec_div_mod.assumption.
52 apply divides_to_div_mod_spec.assumption.assumption.
55 theorem mod_O_to_divides:
56 \forall n,m. O< n \to (mod m n) = O \to divides n m.
58 apply witness n m (div m n).
59 rewrite > plus_n_O (n*div m n).
62 (* perche' hint non lo trova ?*)
67 theorem divides_n_O: \forall n:nat. divides n O.
68 intro. apply witness n O O.apply times_n_O.
71 theorem divides_SO_n: \forall n:nat. divides (S O) n.
72 intro. apply witness (S O) n n. simplify.apply plus_n_O.
75 theorem divides_plus: \forall n,p,q:nat.
76 divides n p \to divides n q \to divides n (p+q).
78 elim H.elim H1. apply witness n (p+q) (n2+n1).
79 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_plus.
82 theorem divides_minus: \forall n,p,q:nat.
83 divides n p \to divides n q \to divides n (p-q).
85 elim H.elim H1. apply witness n (p-q) (n2-n1).
86 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_minus.
89 theorem divides_times: \forall n,m,p,q:nat.
90 divides n p \to divides m q \to divides (n*m) (p*q).
92 elim H.elim H1. apply witness (n*m) (p*q) (n2*n1).
93 rewrite > H2.rewrite > H3.
94 apply trans_eq nat ? (n*(m*(n2*n1))).
95 apply trans_eq nat ? (n*(n2*(m*n1))).
98 apply trans_eq nat ? ((n2*m)*n1).
99 apply sym_eq. apply assoc_times.
100 rewrite > sym_times n2 m.apply assoc_times.
101 apply sym_eq. apply assoc_times.
104 theorem transitive_divides: \forall n,m,p.
105 divides n m \to divides m p \to divides n p.
107 elim H.elim H1. apply witness n p (n2*n1).
108 rewrite > H3.rewrite > H2.
113 theorem divides_to_le : \forall n,m. O < m \to divides n m \to n \le m.
114 intros. elim H1.rewrite > H2.cut O < n2.
115 apply lt_O_n_elim n2 Hcut.intro.rewrite < sym_times.
116 simplify.rewrite < sym_plus.
118 elim le_to_or_lt_eq O n2.
119 assumption.apply le_O_n.
120 absurd O<m.assumption.
121 rewrite > H2.rewrite < H3.rewrite < times_n_O.
125 theorem divides_to_lt_O : \forall n,m. O < m \to divides n m \to O < n.
127 elim le_to_or_lt_eq O n (le_O_n n).
129 rewrite < H3.absurd O < m.assumption.
130 rewrite > H2.rewrite < H3.
131 simplify.exact not_le_Sn_n O.
134 (* boolean divides *)
135 definition divides_b : nat \to nat \to bool \def
136 \lambda n,m :nat. (eqb (mod m n) O).
138 theorem divides_b_to_Prop :
139 \forall n,m:nat. O < n \to O < m \to
140 match divides_b n m with
141 [ true \Rightarrow divides n m
142 | false \Rightarrow \lnot (divides n m)].
145 match eqb (mod m n) O with
146 [ true \Rightarrow divides n m
147 | false \Rightarrow \lnot (divides n m)].
149 intro.simplify.apply mod_O_to_divides.assumption.assumption.
150 intro.simplify.intro.apply H2.apply divides_to_mod_O.assumption.assumption.
153 theorem divides_b_true_to_divides :
154 \forall n,m:nat. O < n \to O < m \to
155 (divides_b n m = true ) \to divides n m.
159 [ true \Rightarrow divides n m
160 | false \Rightarrow \lnot (divides n m)].
161 rewrite < H2.apply divides_b_to_Prop.
162 assumption.assumption.
165 theorem divides_b_false_to_not_divides :
166 \forall n,m:nat. O < n \to O < m \to
167 (divides_b n m = false ) \to \lnot (divides n m).
171 [ true \Rightarrow divides n m
172 | false \Rightarrow \lnot (divides n m)].
173 rewrite < H2.apply divides_b_to_Prop.
174 assumption.assumption.
178 theorem divides_f_pi_f : \forall f:nat \to nat.\forall n,i:nat.
179 i < n \to divides (f i) (pi n f).
180 intros 3.elim n.apply False_ind.apply not_le_Sn_O i H.
182 apply le_n_Sm_elim (S i) n1 H1.
184 apply transitive_divides ? (pi n1 f).
185 apply H.simplify.apply le_S_S_to_le. assumption.
186 apply witness ? ? (f n1).apply sym_times.
189 apply witness ? ? (pi n1 f).reflexivity.
190 apply inj_S.assumption.
193 theorem mod_S_pi: \forall f:nat \to nat.\forall n,i:nat.
194 i < n \to (S O) < (f i) \to mod (S (pi n f)) (f i) = (S O).
195 intros.cut mod (pi n f) (f i) = O.
197 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
198 rewrite > Hcut.assumption.
199 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
200 apply divides_f_pi_f.assumption.
203 (* divides and fact *)
204 theorem divides_fact : \forall n,i:nat.
205 O < i \to i \le n \to divides i (fact n).
206 intros 3.elim n.absurd O<i.assumption.apply le_n_O_elim i H1.
208 change with divides i ((S n1)*(fact n1)).
209 apply le_n_Sm_elim i n1 H2.
211 apply transitive_divides ? (fact n1).
212 apply H1.apply le_S_S_to_le. assumption.
213 apply witness ? ? (S n1).apply sym_times.
216 apply witness ? ? (fact n1).reflexivity.
219 theorem mod_S_fact: \forall n,i:nat.
220 (S O) < i \to i \le n \to mod (S (fact n)) i = (S O).
221 intros.cut mod (fact n) i = O.
223 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
224 rewrite > Hcut.assumption.
225 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
226 apply divides_fact.apply trans_lt O (S O).apply le_n (S O).assumption.
230 theorem not_divides_S_fact: \forall n,i:nat.
231 (S O) < i \to i \le n \to \not (divides i (S (fact n))).
233 apply divides_b_false_to_not_divides.
234 apply trans_lt O (S O).apply le_n (S O).assumption.
235 simplify.apply le_S_S.apply le_O_n.
236 change with (eqb (mod (S (fact n)) i) O) = false.
237 rewrite > mod_S_fact.simplify.reflexivity.
238 assumption.assumption.
242 definition prime : nat \to Prop \def
243 \lambda n:nat. (S O) < n \land
244 (\forall m:nat. divides m n \to (S O) < m \to m = n).
246 theorem not_prime_O: \lnot (prime O).
247 simplify.intro.elim H.apply not_le_Sn_O (S O) H1.
250 theorem not_prime_SO: \lnot (prime (S O)).
251 simplify.intro.elim H.apply not_le_Sn_n (S O) H1.
254 (* smallest factor *)
255 definition smallest_factor : nat \to nat \def
261 [ O \Rightarrow (S O)
262 | (S q) \Rightarrow min_aux q (S(S q)) (\lambda m.(eqb (mod (S(S q)) m) O))]].
265 theorem example1 : smallest_prime_factor (S(S(S O))) = (S(S(S O))).
266 normalize.reflexivity.
269 theorem example2: smallest_prime_factor (S(S(S(S O)))) = (S(S O)).
270 normalize.reflexivity.
273 theorem example3 : smallest_prime_factor (S(S(S(S(S(S(S O))))))) = (S(S(S(S(S(S(S O))))))).
274 simplify.reflexivity.
277 (* not sure this is what we need *)
278 theorem lt_S_O_smallest_factor:
279 \forall n:nat. (S O) < n \to (S O) < (smallest_factor n).
281 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
282 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
285 S O < min_aux m1 (S(S m1)) (\lambda m.(eqb (mod (S(S m1)) m) O)).
286 apply lt_to_le_to_lt ? (S (S O)).
288 cut (S(S O)) = (S(S m1)) - m1.
291 apply sym_eq.apply plus_to_minus.apply le_S.apply le_n_Sn.
292 rewrite < sym_plus.simplify.reflexivity.
295 theorem divides_smallest_factor_n :
296 \forall n:nat. (S O) < n \to divides (smallest_factor n) n.
298 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
299 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
301 apply divides_b_true_to_divides.
302 apply trans_lt ? (S O).apply le_n (S O).apply lt_S_O_smallest_factor ? H.
303 apply trans_lt ? (S O).apply le_n (S O).assumption.
305 eqb (mod (S(S m1)) (min_aux m1 (S(S m1))
306 (\lambda m.(eqb (mod (S(S m1)) m) O)))) O = true.
307 apply f_min_aux_true.
308 apply ex_intro nat ? (S(S m1)).
310 apply le_minus_m.apply le_n.
311 rewrite > mod_n_n.reflexivity.
312 apply trans_lt ? (S O).apply le_n (S O).assumption.
315 theorem le_smallest_factor_n :
316 \forall n:nat. smallest_factor n \le n.
317 intro.apply nat_case n.simplify.reflexivity.
318 intro.apply nat_case m.simplify.reflexivity.
319 intro.apply divides_to_le.
320 simplify.apply le_S_S.apply le_O_n.
321 apply divides_smallest_factor_n.
322 simplify.apply le_S_S.apply le_S_S. apply le_O_n.
325 theorem lt_smallest_factor_to_not_divides: \forall n,i:nat.
326 (S O) < n \to (S O) < i \to i < (smallest_factor n) \to \lnot (divides i n).
328 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
329 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
331 apply divides_b_false_to_not_divides.
332 apply trans_lt O (S O).apply le_n (S O).assumption.
333 apply trans_lt O (S O).apply le_n (S O).assumption.
334 change with (eqb (mod (S(S m1)) i) O) = false.
335 apply lt_min_aux_to_false
336 (\lambda i:nat.eqb (mod (S(S m1)) i) O) (S(S m1)) m1 i.
337 cut (S(S O)) = (S(S m1)-m1).
338 rewrite < Hcut.exact H1.
339 apply sym_eq. apply plus_to_minus.
340 apply le_S.apply le_n_Sn.
341 rewrite < sym_plus.simplify.reflexivity.
345 theorem prime_smallest_factor_n :
346 \forall n:nat. (S O) < n \to prime (smallest_factor n).
347 intro. change with (S(S O)) \le n \to (S O) < (smallest_factor n) \land
348 (\forall m:nat. divides m (smallest_factor n) \to (S O) < m \to m = (smallest_factor n)).
350 apply lt_S_O_smallest_factor.assumption.
352 cut le m (smallest_factor n).
353 elim le_to_or_lt_eq m (smallest_factor n) Hcut.
355 apply transitive_divides m (smallest_factor n).
357 apply divides_smallest_factor_n.
359 apply lt_smallest_factor_to_not_divides.
360 exact H.assumption.assumption.assumption.
362 apply trans_lt O (S O).
364 apply lt_S_O_smallest_factor.
369 theorem prime_to_smallest_factor: \forall n. prime n \to
370 smallest_factor n = n.
371 intro.apply nat_case n.intro.apply False_ind.apply not_prime_O H.
372 intro.apply nat_case m.intro.apply False_ind.apply not_prime_SO H.
375 (S O) < (S(S m1)) \land
376 (\forall m:nat. divides m (S(S m1)) \to (S O) < m \to m = (S(S m1))) \to
377 smallest_factor (S(S m1)) = (S(S m1)).
378 intro.elim H.apply H2.
379 apply divides_smallest_factor_n.
381 apply lt_S_O_smallest_factor.
385 (* a number n > O is prime iff its smallest factor is n *)
386 definition primeb \def \lambda n:nat.
388 [ O \Rightarrow false
391 [ O \Rightarrow false
392 | (S q) \Rightarrow eqb (smallest_factor (S(S q))) (S(S q))]].
395 theorem example4 : primeb (S(S(S O))) = true.
396 normalize.reflexivity.
399 theorem example5 : primeb (S(S(S(S(S(S O)))))) = false.
400 normalize.reflexivity.
403 theorem example6 : primeb (S(S(S(S((S(S(S(S(S(S(S O)))))))))))) = true.
404 normalize.reflexivity.
407 theorem example7 : primeb (S(S(S(S(S(S((S(S(S(S((S(S(S(S(S(S(S O))))))))))))))))))) = true.
408 normalize.reflexivity.
411 theorem primeb_to_Prop: \forall n.
413 [ true \Rightarrow prime n
414 | false \Rightarrow \not (prime n)].
416 apply nat_case n.simplify.intro.elim H.apply not_le_Sn_O (S O) H1.
417 intro.apply nat_case m.simplify.intro.elim H.apply not_le_Sn_n (S O) H1.
420 match eqb (smallest_factor (S(S m1))) (S(S m1)) with
421 [ true \Rightarrow prime (S(S m1))
422 | false \Rightarrow \not (prime (S(S m1)))].
423 apply eqb_elim (smallest_factor (S(S m1))) (S(S m1)).
424 intro.change with prime (S(S m1)).
426 apply prime_smallest_factor_n.
427 simplify.apply le_S_S.apply le_S_S.apply le_O_n.
428 intro.change with \not (prime (S(S m1))).
429 change with prime (S(S m1)) \to False.
431 apply prime_to_smallest_factor.
435 theorem primeb_true_to_prime : \forall n:nat.
436 primeb n = true \to prime n.
439 [ true \Rightarrow prime n
440 | false \Rightarrow \not (prime n)].
442 apply primeb_to_Prop.
445 theorem primeb_false_to_not_prime : \forall n:nat.
446 primeb n = false \to \not (prime n).
449 [ true \Rightarrow prime n
450 | false \Rightarrow \not (prime n)].
452 apply primeb_to_Prop.
455 theorem decidable_prime : \forall n:nat.decidable (prime n).
456 intro.change with (prime n) \lor \not (prime n).
459 [ true \Rightarrow prime n
460 | false \Rightarrow \not (prime n)] \to (prime n) \lor \not (prime n).
461 apply Hcut.apply primeb_to_Prop.
462 elim (primeb n).left.apply H.right.apply H.
465 theorem prime_to_primeb_true: \forall n:nat.
466 prime n \to primeb n = true.
468 cut match (primeb n) with
469 [ true \Rightarrow prime n
470 | false \Rightarrow \not (prime n)] \to ((primeb n) = true).
471 apply Hcut.apply primeb_to_Prop.
472 elim primeb n.reflexivity.
473 absurd (prime n).assumption.assumption.
476 theorem not_prime_to_primeb_false: \forall n:nat.
477 \not(prime n) \to primeb n = false.
479 cut match (primeb n) with
480 [ true \Rightarrow prime n
481 | false \Rightarrow \not (prime n)] \to ((primeb n) = false).
482 apply Hcut.apply primeb_to_Prop.
484 absurd (prime n).assumption.assumption.
488 (* upper bound by Bertrand's conjecture. *)
489 (* Too difficult to prove.
490 let rec nth_prime n \def
492 [ O \Rightarrow (S(S O))
494 let previous_prime \def S (nth_prime p) in
495 min_aux previous_prime ((S(S O))*previous_prime) primeb].
497 theorem example8 : nth_prime (S(S O)) = (S(S(S(S(S O))))).
498 normalize.reflexivity.
501 theorem example9 : nth_prime (S(S(S O))) = (S(S(S(S(S(S(S O))))))).
502 normalize.reflexivity.
505 theorem example10 : nth_prime (S(S(S(S O)))) = (S(S(S(S(S(S(S(S(S(S(S O))))))))))).
506 normalize.reflexivity.
509 theorem smallest_factor_fact: \forall n:nat.
510 n < smallest_factor (S (fact n)).
513 change with smallest_factor (S (fact n)) \le n \to False.intro.
514 apply not_divides_S_fact n (smallest_factor(S (fact n))) ? ?.
515 apply divides_smallest_factor_n.
516 simplify.apply le_S_S.apply le_SO_fact.
517 apply lt_S_O_smallest_factor.
518 simplify.apply le_S_S.apply le_SO_fact.
522 (* mi sembra che il problem sia ex *)
523 theorem ex_prime: \forall n. (S O) \le n \to ex nat (\lambda m.
524 n < m \land m \le (S (fact n)) \land (prime m)).
527 apply ex_intro nat ? (S(S O)).
528 split.split.apply le_n (S(S O)).
529 apply le_n (S(S O)).apply primeb_to_Prop (S(S O)).
530 apply ex_intro nat ? (smallest_factor (S (fact (S n1)))).
532 apply smallest_factor_fact.
533 apply le_smallest_factor_n.
534 (* ancora hint non lo trova *)
535 apply prime_smallest_factor_n.
536 change with (S(S O)) \le S (fact (S n1)).
537 apply le_S.apply le_SSO_fact.
538 simplify.apply le_S_S.assumption.
541 let rec nth_prime n \def
543 [ O \Rightarrow (S(S O))
545 let previous_prime \def (nth_prime p) in
546 let upper_bound \def S (fact previous_prime) in
547 min_aux (upper_bound - (S previous_prime)) upper_bound primeb].
549 (* it works, but nth_prime 4 takes already a few minutes -
550 it must compute factorial of 7 ...
552 theorem example11 : nth_prime (S(S O)) = (S(S(S(S(S O))))).
553 normalize.reflexivity.
556 theorem example12: nth_prime (S(S(S O))) = (S(S(S(S(S(S(S O))))))).
557 normalize.reflexivity.
560 theorem example13 : nth_prime (S(S(S(S O)))) = (S(S(S(S(S(S(S(S(S(S(S O))))))))))).
561 normalize.reflexivity.
564 theorem prime_nth_prime : \forall n:nat.prime (nth_prime n).
567 change with prime (S(S O)).
568 apply primeb_to_Prop (S(S O)).
570 (* ammirare la resa del letin !! *)
572 let previous_prime \def (nth_prime m) in
573 let upper_bound \def S (fact previous_prime) in
574 prime (min_aux (upper_bound - (S previous_prime)) upper_bound primeb).
575 apply primeb_true_to_prime.
576 apply f_min_aux_true.
577 apply ex_intro nat ? (smallest_factor (S (fact (nth_prime m)))).
579 cut S (fact (nth_prime m))-(S (fact (nth_prime m)) - (S (nth_prime m))) = (S (nth_prime m)).
580 rewrite > Hcut.exact smallest_factor_fact (nth_prime m).
581 (* maybe we could factorize this proof *)
584 apply plus_minus_m_m.
587 apply le_smallest_factor_n.
588 apply prime_to_primeb_true.
589 apply prime_smallest_factor_n.
590 change with (S(S O)) \le S (fact (nth_prime m)).
591 apply le_S_S.apply le_SO_fact.