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 interpretation "divides" 'divides n m = (cic:/matita/nat/primes/divides.ind#xpointer(1/1) n m).
26 interpretation "not divides" 'ndivides n m =
27 (cic:/matita/logic/connectives/Not.con (cic:/matita/nat/primes/divides.ind#xpointer(1/1) n m)).
29 theorem reflexive_divides : reflexive nat divides.
32 exact witness x x (S O) (times_n_SO x).
35 theorem divides_to_div_mod_spec :
36 \forall n,m. O < n \to n \divides m \to div_mod_spec m n (m / n) O.
37 intros.elim H1.rewrite > H2.
38 constructor 1.assumption.
39 apply lt_O_n_elim n H.intros.
41 rewrite > div_times.apply sym_times.
44 theorem div_mod_spec_to_divides :
45 \forall n,m,p. div_mod_spec m n p O \to n \divides m.
49 rewrite > plus_n_O (p*n).assumption.
52 theorem divides_to_mod_O:
53 \forall n,m. O < n \to n \divides m \to (m \mod n) = O.
54 intros.apply div_mod_spec_to_eq2 m n (m / n) (m \mod n) (m / n) O.
55 apply div_mod_spec_div_mod.assumption.
56 apply divides_to_div_mod_spec.assumption.assumption.
59 theorem mod_O_to_divides:
60 \forall n,m. O< n \to (m \mod n) = O \to n \divides m.
62 apply witness n m (m / n).
63 rewrite > plus_n_O (n * (m / n)).
66 (* Andrea: perche' hint non lo trova ?*)
71 theorem divides_n_O: \forall n:nat. n \divides O.
72 intro. apply witness n O O.apply times_n_O.
75 theorem divides_n_n: \forall n:nat. n \divides n.
76 intro. apply witness n n (S O).apply times_n_SO.
79 theorem divides_SO_n: \forall n:nat. (S O) \divides n.
80 intro. apply witness (S O) n n. simplify.apply plus_n_O.
83 theorem divides_plus: \forall n,p,q:nat.
84 n \divides p \to n \divides q \to n \divides p+q.
86 elim H.elim H1. apply witness n (p+q) (n2+n1).
87 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_plus.
90 theorem divides_minus: \forall n,p,q:nat.
91 divides n p \to divides n q \to divides n (p-q).
93 elim H.elim H1. apply witness n (p-q) (n2-n1).
94 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_minus.
97 theorem divides_times: \forall n,m,p,q:nat.
98 n \divides p \to m \divides q \to n*m \divides p*q.
100 elim H.elim H1. apply witness (n*m) (p*q) (n2*n1).
101 rewrite > H2.rewrite > H3.
102 apply trans_eq nat ? (n*(m*(n2*n1))).
103 apply trans_eq nat ? (n*(n2*(m*n1))).
106 apply trans_eq nat ? ((n2*m)*n1).
107 apply sym_eq. apply assoc_times.
108 rewrite > sym_times n2 m.apply assoc_times.
109 apply sym_eq. apply assoc_times.
112 theorem transitive_divides: transitive ? divides.
115 elim H.elim H1. apply witness x z (n2*n).
116 rewrite > H3.rewrite > H2.
120 variant trans_divides: \forall n,m,p.
121 n \divides m \to m \divides p \to n \divides p \def transitive_divides.
123 theorem eq_mod_to_divides:\forall n,m,p. O< p \to
124 mod n p = mod m p \to divides p (n-m).
126 cut n \le m \or \not n \le m.
132 apply eq_minus_n_m_O.
134 apply witness p (n-m) ((div n p)-(div m p)).
135 rewrite > distr_times_minus.
137 rewrite > sym_times p.
138 cut (div n p)*p = n - (mod n p).
140 rewrite > eq_minus_minus_minus_plus.
143 rewrite < div_mod.reflexivity.
150 apply decidable_le n m.
154 theorem divides_to_le : \forall n,m. O < m \to n \divides m \to n \le m.
155 intros. elim H1.rewrite > H2.cut O < n2.
156 apply lt_O_n_elim n2 Hcut.intro.rewrite < sym_times.
157 simplify.rewrite < sym_plus.
159 elim le_to_or_lt_eq O n2.
161 absurd O<m.assumption.
162 rewrite > H2.rewrite < H3.rewrite < times_n_O.
167 theorem divides_to_lt_O : \forall n,m. O < m \to n \divides m \to O < n.
169 elim le_to_or_lt_eq O n (le_O_n n).
171 rewrite < H3.absurd O < m.assumption.
172 rewrite > H2.rewrite < H3.
173 simplify.exact not_le_Sn_n O.
176 (* boolean divides *)
177 definition divides_b : nat \to nat \to bool \def
178 \lambda n,m :nat. (eqb (m \mod n) O).
180 theorem divides_b_to_Prop :
181 \forall n,m:nat. O < n \to
182 match divides_b n m with
183 [ true \Rightarrow n \divides m
184 | false \Rightarrow n \ndivides m].
187 match eqb (m \mod n) O with
188 [ true \Rightarrow n \divides m
189 | false \Rightarrow n \ndivides m].
191 intro.simplify.apply mod_O_to_divides.assumption.assumption.
192 intro.simplify.intro.apply H1.apply divides_to_mod_O.assumption.assumption.
195 theorem divides_b_true_to_divides :
196 \forall n,m:nat. O < n \to
197 (divides_b n m = true ) \to n \divides m.
201 [ true \Rightarrow n \divides m
202 | false \Rightarrow n \ndivides m].
203 rewrite < H1.apply divides_b_to_Prop.
207 theorem divides_b_false_to_not_divides :
208 \forall n,m:nat. O < n \to
209 (divides_b n m = false ) \to n \ndivides m.
213 [ true \Rightarrow n \divides m
214 | false \Rightarrow n \ndivides m].
215 rewrite < H1.apply divides_b_to_Prop.
219 theorem decidable_divides: \forall n,m:nat.O < n \to
220 decidable (n \divides m).
221 intros.change with (n \divides m) \lor n \ndivides m.
223 match divides_b n m with
224 [ true \Rightarrow n \divides m
225 | false \Rightarrow n \ndivides m] \to n \divides m \lor n \ndivides m.
226 apply Hcut.apply divides_b_to_Prop.assumption.
227 elim (divides_b n m).left.apply H1.right.apply H1.
230 theorem divides_to_divides_b_true : \forall n,m:nat. O < n \to
231 n \divides m \to divides_b n m = true.
233 cut match (divides_b n m) with
234 [ true \Rightarrow n \divides m
235 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = true).
236 apply Hcut.apply divides_b_to_Prop.assumption.
237 elim divides_b n m.reflexivity.
238 absurd (n \divides m).assumption.assumption.
241 theorem not_divides_to_divides_b_false: \forall n,m:nat. O < n \to
242 \lnot(n \divides m) \to (divides_b n m) = false.
244 cut match (divides_b n m) with
245 [ true \Rightarrow n \divides m
246 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = false).
247 apply Hcut.apply divides_b_to_Prop.assumption.
249 absurd (n \divides m).assumption.assumption.
254 theorem divides_f_pi_f : \forall f:nat \to nat.\forall n,m,i:nat.
255 m \le i \to i \le n+m \to f i \divides pi n f m.
256 intros 5.elim n.simplify.
257 cut i = m.rewrite < Hcut.apply divides_n_n.
258 apply antisymmetric_le.assumption.assumption.
260 cut i < S n1+m \lor i = S n1 + m.
262 apply transitive_divides ? (pi n1 f m).
263 apply H1.apply le_S_S_to_le. assumption.
264 apply witness ? ? (f (S n1+m)).apply sym_times.
266 apply witness ? ? (pi n1 f m).reflexivity.
267 apply le_to_or_lt_eq.assumption.
271 theorem mod_S_pi: \forall f:nat \to nat.\forall n,i:nat.
272 i < n \to (S O) < (f i) \to (S (pi n f)) \mod (f i) = (S O).
273 intros.cut (pi n f) \mod (f i) = O.
275 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
276 rewrite > Hcut.assumption.
277 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
278 apply divides_f_pi_f.assumption.
282 (* divides and fact *)
283 theorem divides_fact : \forall n,i:nat.
284 O < i \to i \le n \to i \divides n!.
285 intros 3.elim n.absurd O<i.assumption.apply le_n_O_elim i H1.
287 change with i \divides (S n1)*n1!.
288 apply le_n_Sm_elim i n1 H2.
290 apply transitive_divides ? n1!.
291 apply H1.apply le_S_S_to_le. assumption.
292 apply witness ? ? (S n1).apply sym_times.
295 apply witness ? ? n1!.reflexivity.
298 theorem mod_S_fact: \forall n,i:nat.
299 (S O) < i \to i \le n \to (S n!) \mod i = (S O).
300 intros.cut n! \mod i = O.
302 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
303 rewrite > Hcut.assumption.
304 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
305 apply divides_fact.apply trans_lt O (S O).apply le_n (S O).assumption.
309 theorem not_divides_S_fact: \forall n,i:nat.
310 (S O) < i \to i \le n \to i \ndivides S n!.
312 apply divides_b_false_to_not_divides.
313 apply trans_lt O (S O).apply le_n (S O).assumption.
314 change with (eqb ((S n!) \mod i) O) = false.
315 rewrite > mod_S_fact.simplify.reflexivity.
316 assumption.assumption.
320 definition prime : nat \to Prop \def
321 \lambda n:nat. (S O) < n \land
322 (\forall m:nat. m \divides n \to (S O) < m \to m = n).
324 theorem not_prime_O: \lnot (prime O).
325 simplify.intro.elim H.apply not_le_Sn_O (S O) H1.
328 theorem not_prime_SO: \lnot (prime (S O)).
329 simplify.intro.elim H.apply not_le_Sn_n (S O) H1.
332 (* smallest factor *)
333 definition smallest_factor : nat \to nat \def
339 [ O \Rightarrow (S O)
340 | (S q) \Rightarrow min_aux q (S(S q)) (\lambda m.(eqb ((S(S q)) \mod m) O))]].
343 theorem example1 : smallest_prime_factor (S(S(S O))) = (S(S(S O))).
344 normalize.reflexivity.
347 theorem example2: smallest_prime_factor (S(S(S(S O)))) = (S(S O)).
348 normalize.reflexivity.
351 theorem example3 : smallest_prime_factor (S(S(S(S(S(S(S O))))))) = (S(S(S(S(S(S(S O))))))).
352 simplify.reflexivity.
355 theorem lt_SO_smallest_factor:
356 \forall n:nat. (S O) < n \to (S O) < (smallest_factor n).
358 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
359 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
362 S O < min_aux m1 (S(S m1)) (\lambda m.(eqb ((S(S m1)) \mod m) O)).
363 apply lt_to_le_to_lt ? (S (S O)).
365 cut (S(S O)) = (S(S m1)) - m1.
368 apply sym_eq.apply plus_to_minus.
369 rewrite < sym_plus.simplify.reflexivity.
372 theorem lt_O_smallest_factor: \forall n:nat. O < n \to O < (smallest_factor n).
374 apply nat_case n.intro.apply False_ind.apply not_le_Sn_n O H.
375 intro.apply nat_case m.intro.
377 intros.apply trans_lt ? (S O).
378 simplify. apply le_n.
379 apply lt_SO_smallest_factor.simplify. apply le_S_S.
380 apply le_S_S.apply le_O_n.
383 theorem divides_smallest_factor_n :
384 \forall n:nat. O < n \to smallest_factor n \divides n.
386 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O O H.
387 intro.apply nat_case m.intro. simplify.
388 apply witness ? ? (S O). simplify.reflexivity.
390 apply divides_b_true_to_divides.
391 apply lt_O_smallest_factor ? H.
393 eqb ((S(S m1)) \mod (min_aux m1 (S(S m1))
394 (\lambda m.(eqb ((S(S m1)) \mod m) O)))) O = true.
395 apply f_min_aux_true.
396 apply ex_intro nat ? (S(S m1)).
398 apply le_minus_m.apply le_n.
399 rewrite > mod_n_n.reflexivity.
400 apply trans_lt ? (S O).apply le_n (S O).simplify.
401 apply le_S_S.apply le_S_S.apply le_O_n.
404 theorem le_smallest_factor_n :
405 \forall n:nat. smallest_factor n \le n.
406 intro.apply nat_case n.simplify.reflexivity.
407 intro.apply nat_case m.simplify.reflexivity.
408 intro.apply divides_to_le.
409 simplify.apply le_S_S.apply le_O_n.
410 apply divides_smallest_factor_n.
411 simplify.apply le_S_S.apply le_O_n.
414 theorem lt_smallest_factor_to_not_divides: \forall n,i:nat.
415 (S O) < n \to (S O) < i \to i < (smallest_factor n) \to i \ndivides n.
417 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
418 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
420 apply divides_b_false_to_not_divides.
421 apply trans_lt O (S O).apply le_n (S O).assumption.
422 change with (eqb ((S(S m1)) \mod i) O) = false.
423 apply lt_min_aux_to_false
424 (\lambda i:nat.eqb ((S(S m1)) \mod i) O) (S(S m1)) m1 i.
425 cut (S(S O)) = (S(S m1)-m1).
426 rewrite < Hcut.exact H1.
427 apply sym_eq. apply plus_to_minus.
428 rewrite < sym_plus.simplify.reflexivity.
432 theorem prime_smallest_factor_n :
433 \forall n:nat. (S O) < n \to prime (smallest_factor n).
434 intro. change with (S(S O)) \le n \to (S O) < (smallest_factor n) \land
435 (\forall m:nat. m \divides smallest_factor n \to (S O) < m \to m = (smallest_factor n)).
437 apply lt_SO_smallest_factor.assumption.
439 cut le m (smallest_factor n).
440 elim le_to_or_lt_eq m (smallest_factor n) Hcut.
442 apply transitive_divides m (smallest_factor n).
444 apply divides_smallest_factor_n.
445 apply trans_lt ? (S O). simplify. apply le_n. exact H.
446 apply lt_smallest_factor_to_not_divides.
447 exact H.assumption.assumption.assumption.
449 apply trans_lt O (S O).
451 apply lt_SO_smallest_factor.
456 theorem prime_to_smallest_factor: \forall n. prime n \to
457 smallest_factor n = n.
458 intro.apply nat_case n.intro.apply False_ind.apply not_prime_O H.
459 intro.apply nat_case m.intro.apply False_ind.apply not_prime_SO H.
462 (S O) < (S(S m1)) \land
463 (\forall m:nat. m \divides S(S m1) \to (S O) < m \to m = (S(S m1))) \to
464 smallest_factor (S(S m1)) = (S(S m1)).
465 intro.elim H.apply H2.
466 apply divides_smallest_factor_n.
467 apply trans_lt ? (S O).simplify. apply le_n.assumption.
468 apply lt_SO_smallest_factor.
472 (* a number n > O is prime iff its smallest factor is n *)
473 definition primeb \def \lambda n:nat.
475 [ O \Rightarrow false
478 [ O \Rightarrow false
479 | (S q) \Rightarrow eqb (smallest_factor (S(S q))) (S(S q))]].
482 theorem example4 : primeb (S(S(S O))) = true.
483 normalize.reflexivity.
486 theorem example5 : primeb (S(S(S(S(S(S O)))))) = false.
487 normalize.reflexivity.
490 theorem example6 : primeb (S(S(S(S((S(S(S(S(S(S(S O)))))))))))) = true.
491 normalize.reflexivity.
494 theorem example7 : primeb (S(S(S(S(S(S((S(S(S(S((S(S(S(S(S(S(S O))))))))))))))))))) = true.
495 normalize.reflexivity.
498 theorem primeb_to_Prop: \forall n.
500 [ true \Rightarrow prime n
501 | false \Rightarrow \lnot (prime n)].
503 apply nat_case n.simplify.intro.elim H.apply not_le_Sn_O (S O) H1.
504 intro.apply nat_case m.simplify.intro.elim H.apply not_le_Sn_n (S O) H1.
507 match eqb (smallest_factor (S(S m1))) (S(S m1)) with
508 [ true \Rightarrow prime (S(S m1))
509 | false \Rightarrow \lnot (prime (S(S m1)))].
510 apply eqb_elim (smallest_factor (S(S m1))) (S(S m1)).
511 intro.change with prime (S(S m1)).
513 apply prime_smallest_factor_n.
514 simplify.apply le_S_S.apply le_S_S.apply le_O_n.
515 intro.change with \lnot (prime (S(S m1))).
516 change with prime (S(S m1)) \to False.
518 apply prime_to_smallest_factor.
522 theorem primeb_true_to_prime : \forall n:nat.
523 primeb n = true \to prime n.
526 [ true \Rightarrow prime n
527 | false \Rightarrow \lnot (prime n)].
529 apply primeb_to_Prop.
532 theorem primeb_false_to_not_prime : \forall n:nat.
533 primeb n = false \to \lnot (prime n).
536 [ true \Rightarrow prime n
537 | false \Rightarrow \lnot (prime n)].
539 apply primeb_to_Prop.
542 theorem decidable_prime : \forall n:nat.decidable (prime n).
543 intro.change with (prime n) \lor \lnot (prime n).
546 [ true \Rightarrow prime n
547 | false \Rightarrow \lnot (prime n)] \to (prime n) \lor \lnot (prime n).
548 apply Hcut.apply primeb_to_Prop.
549 elim (primeb n).left.apply H.right.apply H.
552 theorem prime_to_primeb_true: \forall n:nat.
553 prime n \to primeb n = true.
555 cut match (primeb n) with
556 [ true \Rightarrow prime n
557 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = true).
558 apply Hcut.apply primeb_to_Prop.
559 elim primeb n.reflexivity.
560 absurd (prime n).assumption.assumption.
563 theorem not_prime_to_primeb_false: \forall n:nat.
564 \lnot(prime n) \to primeb n = false.
566 cut match (primeb n) with
567 [ true \Rightarrow prime n
568 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = false).
569 apply Hcut.apply primeb_to_Prop.
571 absurd (prime n).assumption.assumption.