]> matita.cs.unibo.it Git - helm.git/blob - matita/library/nat/primes.ma
fixed propagation under Fix/Lambda/Case of coercions, better names are
[helm.git] / matita / library / nat / primes.ma
1 (**************************************************************************)
2 (*       ___                                                                *)
3 (*      ||M||                                                             *)
4 (*      ||A||       A project by Andrea Asperti                           *)
5 (*      ||T||                                                             *)
6 (*      ||I||       Developers:                                           *)
7 (*      ||T||       A.Asperti, C.Sacerdoti Coen,                          *)
8 (*      ||A||       E.Tassi, S.Zacchiroli                                 *)
9 (*      \   /                                                             *)
10 (*       \ /        Matita is distributed under the terms of the          *)
11 (*        v         GNU Lesser General Public License Version 2.1         *)
12 (*                                                                        *)
13 (**************************************************************************)
14
15 set "baseuri" "cic:/matita/nat/primes".
16
17 include "nat/div_and_mod.ma".
18 include "nat/minimization.ma".
19 include "nat/sigma_and_pi.ma".
20 include "nat/factorial.ma".
21
22 inductive divides (n,m:nat) : Prop \def
23 witness : \forall p:nat.m = times n p \to divides n m.
24
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)).
28
29 theorem reflexive_divides : reflexive nat divides.
30 unfold reflexive.
31 intros.
32 exact (witness x x (S O) (times_n_SO x)).
33 qed.
34
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.
40 rewrite < plus_n_O.
41 rewrite > div_times.apply sym_times.
42 qed.
43
44 theorem div_mod_spec_to_divides :
45 \forall n,m,p. div_mod_spec m n p O \to n \divides m.
46 intros.elim H.
47 apply (witness n m p).
48 rewrite < sym_times.
49 rewrite > (plus_n_O (p*n)).assumption.
50 qed.
51
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.
57 qed.
58
59 theorem mod_O_to_divides:
60 \forall n,m. O< n \to (m \mod n) = O \to  n \divides m.
61 intros.
62 apply (witness n m (m / n)).
63 rewrite > (plus_n_O (n * (m / n))).
64 rewrite < H1.
65 rewrite < sym_times.
66 (* Andrea: perche' hint non lo trova ?*)
67 apply div_mod.
68 assumption.
69 qed.
70
71 theorem divides_n_O: \forall n:nat. n \divides O.
72 intro. apply (witness n O O).apply times_n_O.
73 qed.
74
75 theorem divides_n_n: \forall n:nat. n \divides n.
76 intro. apply (witness n n (S O)).apply times_n_SO.
77 qed.
78
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.
81 qed.
82
83 theorem divides_plus: \forall n,p,q:nat. 
84 n \divides p \to n \divides q \to n \divides p+q.
85 intros.
86 elim H.elim H1. apply (witness n (p+q) (n2+n1)).
87 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_plus.
88 qed.
89
90 theorem divides_minus: \forall n,p,q:nat. 
91 divides n p \to divides n q \to divides n (p-q).
92 intros.
93 elim H.elim H1. apply (witness n (p-q) (n2-n1)).
94 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_minus.
95 qed.
96
97 theorem divides_times: \forall n,m,p,q:nat. 
98 n \divides p \to m \divides q \to n*m \divides p*q.
99 intros.
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)))).
104 apply assoc_times.
105 apply eq_f.
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.
110 qed.
111
112 theorem transitive_divides: transitive ? divides.
113 unfold.
114 intros.
115 elim H.elim H1. apply (witness x z (n2*n)).
116 rewrite > H3.rewrite > H2.
117 apply assoc_times.
118 qed.
119
120 variant trans_divides: \forall n,m,p. 
121  n \divides m \to m \divides p \to n \divides p \def transitive_divides.
122
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).
125 intros.
126 cut (n \le m \or \not n \le m).
127 elim Hcut.
128 cut (n-m=O).
129 rewrite > Hcut1.
130 apply (witness p O O).
131 apply times_n_O.
132 apply eq_minus_n_m_O.
133 assumption.
134 apply (witness p (n-m) ((div n p)-(div m p))).
135 rewrite > distr_times_minus.
136 rewrite > sym_times.
137 rewrite > (sym_times p).
138 cut ((div n p)*p = n - (mod n p)).
139 rewrite > Hcut1.
140 rewrite > eq_minus_minus_minus_plus.
141 rewrite > sym_plus.
142 rewrite > H1.
143 rewrite < div_mod.reflexivity.
144 assumption.
145 apply sym_eq.
146 apply plus_to_minus.
147 rewrite > sym_plus.
148 apply div_mod.
149 assumption.
150 apply (decidable_le n m).
151 qed.
152
153 theorem antisymmetric_divides: antisymmetric nat divides.
154 unfold antisymmetric.intros.elim H. elim H1.
155 apply (nat_case1 n2).intro.
156 rewrite > H3.rewrite > H2.rewrite > H4.
157 rewrite < times_n_O.reflexivity.
158 intros.
159 apply (nat_case1 n).intro.
160 rewrite > H2.rewrite > H3.rewrite > H5.
161 rewrite < times_n_O.reflexivity.
162 intros.
163 apply antisymmetric_le.
164 rewrite > H2.rewrite > times_n_SO in \vdash (? % ?).
165 apply le_times_r.rewrite > H4.apply le_S_S.apply le_O_n.
166 rewrite > H3.rewrite > times_n_SO in \vdash (? % ?).
167 apply le_times_r.rewrite > H5.apply le_S_S.apply le_O_n.
168 qed.
169
170 (* divides le *)
171 theorem divides_to_le : \forall n,m. O < m \to n \divides m \to n \le m.
172 intros. elim H1.rewrite > H2.cut (O < n2).
173 apply (lt_O_n_elim n2 Hcut).intro.rewrite < sym_times.
174 simplify.rewrite < sym_plus.
175 apply le_plus_n.
176 elim (le_to_or_lt_eq O n2).
177 assumption.
178 absurd (O<m).assumption.
179 rewrite > H2.rewrite < H3.rewrite < times_n_O.
180 apply (not_le_Sn_n O).
181 apply le_O_n.
182 qed.
183
184 theorem divides_to_lt_O : \forall n,m. O < m \to n \divides m \to O < n.
185 intros.elim H1.
186 elim (le_to_or_lt_eq O n (le_O_n n)).
187 assumption.
188 rewrite < H3.absurd (O < m).assumption.
189 rewrite > H2.rewrite < H3.
190 simplify.exact (not_le_Sn_n O).
191 qed.
192
193 (* boolean divides *)
194 definition divides_b : nat \to nat \to bool \def
195 \lambda n,m :nat. (eqb (m \mod n) O).
196
197 theorem divides_b_to_Prop :
198 \forall n,m:nat. O < n \to
199 match divides_b n m with
200 [ true \Rightarrow n \divides m
201 | false \Rightarrow n \ndivides m].
202 intros.unfold divides_b.
203 apply eqb_elim.
204 intro.simplify.apply mod_O_to_divides.assumption.assumption.
205 intro.simplify.unfold Not.intro.apply H1.apply divides_to_mod_O.assumption.assumption.
206 qed.
207
208 theorem divides_b_true_to_divides1:
209 \forall n,m:nat. O < n \to
210 (divides_b n m = true ) \to n \divides m.
211 intros.
212 change with 
213 match true with
214 [ true \Rightarrow n \divides m
215 | false \Rightarrow n \ndivides m].
216 rewrite < H1.apply divides_b_to_Prop.
217 assumption.
218 qed.
219
220 theorem divides_b_true_to_divides:
221 \forall n,m:nat. divides_b n m = true \to n \divides m.
222 intros 2.apply (nat_case n)
223   [apply (nat_case m)
224     [intro.apply divides_n_n
225     |simplify.intros.apply False_ind.
226      apply not_eq_true_false.apply sym_eq.assumption
227     ]
228   |intros.
229    apply divides_b_true_to_divides1
230     [apply lt_O_S|assumption]
231   ]
232 qed.
233
234 theorem divides_b_false_to_not_divides1:
235 \forall n,m:nat. O < n \to
236 (divides_b n m = false ) \to n \ndivides m.
237 intros.
238 change with 
239 match false with
240 [ true \Rightarrow n \divides m
241 | false \Rightarrow n \ndivides m].
242 rewrite < H1.apply divides_b_to_Prop.
243 assumption.
244 qed.
245
246 theorem divides_b_false_to_not_divides:
247 \forall n,m:nat. divides_b n m = false \to n \ndivides m.
248 intros 2.apply (nat_case n)
249   [apply (nat_case m)
250     [simplify.unfold Not.intros.
251      apply not_eq_true_false.assumption
252     |unfold Not.intros.elim H1.
253      apply (not_eq_O_S m1).apply sym_eq.
254      assumption
255     ]
256   |intros.
257    apply divides_b_false_to_not_divides1
258     [apply lt_O_S|assumption]
259   ]
260 qed.
261
262 theorem decidable_divides: \forall n,m:nat.O < n \to
263 decidable (n \divides m).
264 intros.unfold decidable.
265 cut 
266 (match divides_b n m with
267 [ true \Rightarrow n \divides m
268 | false \Rightarrow n \ndivides m] \to n \divides m \lor n \ndivides m).
269 apply Hcut.apply divides_b_to_Prop.assumption.
270 elim (divides_b n m).left.apply H1.right.apply H1.
271 qed.
272
273 theorem divides_to_divides_b_true : \forall n,m:nat. O < n \to
274 n \divides m \to divides_b n m = true.
275 intros.
276 cut (match (divides_b n m) with
277 [ true \Rightarrow n \divides m
278 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = true)).
279 apply Hcut.apply divides_b_to_Prop.assumption.
280 elim (divides_b n m).reflexivity.
281 absurd (n \divides m).assumption.assumption.
282 qed.
283
284 theorem not_divides_to_divides_b_false: \forall n,m:nat. O < n \to
285 \lnot(n \divides m) \to (divides_b n m) = false.
286 intros.
287 cut (match (divides_b n m) with
288 [ true \Rightarrow n \divides m
289 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = false)).
290 apply Hcut.apply divides_b_to_Prop.assumption.
291 elim (divides_b n m).
292 absurd (n \divides m).assumption.assumption.
293 reflexivity.
294 qed.
295
296 theorem divides_b_true_to_lt_O: \forall n,m. O < n \to divides_b m n = true \to O < m.
297 intros.
298 elim (le_to_or_lt_eq ? ? (le_O_n m))
299   [assumption
300   |apply False_ind.
301    elim H1.
302    rewrite < H2 in H1.
303    simplify in H1.
304    apply (lt_to_not_eq O n H).
305    apply sym_eq.
306    apply eqb_true_to_eq.
307    assumption
308   ]
309 qed.
310
311 (* divides and pi *)
312 theorem divides_f_pi_f : \forall f:nat \to nat.\forall n,m,i:nat. 
313 m \le i \to i \le n+m \to f i \divides pi n f m.
314 intros 5.elim n.simplify.
315 cut (i = m).rewrite < Hcut.apply divides_n_n.
316 apply antisymmetric_le.assumption.assumption.
317 simplify.
318 cut (i < S n1+m \lor i = S n1 + m).
319 elim Hcut.
320 apply (transitive_divides ? (pi n1 f m)).
321 apply H1.apply le_S_S_to_le. assumption.
322 apply (witness ? ? (f (S n1+m))).apply sym_times.
323 rewrite > H3.
324 apply (witness ? ? (pi n1 f m)).reflexivity.
325 apply le_to_or_lt_eq.assumption.
326 qed.
327
328 (*
329 theorem mod_S_pi: \forall f:nat \to nat.\forall n,i:nat. 
330 i < n \to (S O) < (f i) \to (S (pi n f)) \mod (f i) = (S O).
331 intros.cut (pi n f) \mod (f i) = O.
332 rewrite < Hcut.
333 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
334 rewrite > Hcut.assumption.
335 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
336 apply divides_f_pi_f.assumption.
337 qed.
338 *)
339
340 (* divides and fact *)
341 theorem divides_fact : \forall n,i:nat. 
342 O < i \to i \le n \to i \divides n!.
343 intros 3.elim n.absurd (O<i).assumption.apply (le_n_O_elim i H1).
344 apply (not_le_Sn_O O).
345 change with (i \divides (S n1)*n1!).
346 apply (le_n_Sm_elim i n1 H2).
347 intro.
348 apply (transitive_divides ? n1!).
349 apply H1.apply le_S_S_to_le. assumption.
350 apply (witness ? ? (S n1)).apply sym_times.
351 intro.
352 rewrite > H3.
353 apply (witness ? ? n1!).reflexivity.
354 qed.
355
356 theorem mod_S_fact: \forall n,i:nat. 
357 (S O) < i \to i \le n \to (S n!) \mod i = (S O).
358 intros.cut (n! \mod i = O).
359 rewrite < Hcut.
360 apply mod_S.apply (trans_lt O (S O)).apply (le_n (S O)).assumption.
361 rewrite > Hcut.assumption.
362 apply divides_to_mod_O.apply (trans_lt O (S O)).apply (le_n (S O)).assumption.
363 apply divides_fact.apply (trans_lt O (S O)).apply (le_n (S O)).assumption.
364 assumption.
365 qed.
366
367 theorem not_divides_S_fact: \forall n,i:nat. 
368 (S O) < i \to i \le n \to i \ndivides S n!.
369 intros.
370 apply divides_b_false_to_not_divides.
371 unfold divides_b.
372 rewrite > mod_S_fact[simplify.reflexivity|assumption|assumption].
373 qed.
374
375 (* prime *)
376 definition prime : nat \to  Prop \def
377 \lambda n:nat. (S O) < n \land 
378 (\forall m:nat. m \divides n \to (S O) < m \to  m = n).
379
380 theorem not_prime_O: \lnot (prime O).
381 unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_O (S O) H1).
382 qed.
383
384 theorem not_prime_SO: \lnot (prime (S O)).
385 unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_n (S O) H1).
386 qed.
387
388 theorem prime_to_lt_O: \forall p. prime p \to O < p.
389 intros.elim H.apply lt_to_le.assumption.
390 qed.
391
392 (* smallest factor *)
393 definition smallest_factor : nat \to nat \def
394 \lambda n:nat. 
395 match n with
396 [ O \Rightarrow O
397 | (S p) \Rightarrow 
398   match p with
399   [ O \Rightarrow (S O)
400   | (S q) \Rightarrow min_aux q (S (S O)) (\lambda m.(eqb ((S(S q)) \mod m) O))]].
401
402 (* it works !
403 theorem example1 : smallest_factor (S(S(S O))) = (S(S(S O))).
404 normalize.reflexivity.
405 qed.
406
407 theorem example2: smallest_factor (S(S(S(S O)))) = (S(S O)).
408 normalize.reflexivity.
409 qed.
410
411 theorem example3 : smallest_factor (S(S(S(S(S(S(S O))))))) = (S(S(S(S(S(S(S O))))))).
412 simplify.reflexivity.
413 qed. *)
414
415 theorem lt_SO_smallest_factor: 
416 \forall n:nat. (S O) < n \to (S O) < (smallest_factor n).
417 intro.
418 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O (S O) H).
419 intro.apply (nat_case m).intro. apply False_ind.apply (not_le_Sn_n (S O) H).
420 intros.
421 change with 
422 (S O < min_aux m1 (S (S O)) (\lambda m.(eqb ((S(S m1)) \mod m) O))).
423 apply (lt_to_le_to_lt ? (S (S O))).
424 apply (le_n (S(S O))).
425 cut ((S(S O)) = (S(S m1)) - m1).
426 rewrite > Hcut.
427 apply le_min_aux.
428 apply sym_eq.apply plus_to_minus.
429 rewrite < sym_plus.simplify.reflexivity.
430 qed.
431
432 theorem lt_O_smallest_factor: \forall n:nat. O < n \to O < (smallest_factor n).
433 intro.
434 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_n O H).
435 intro.apply (nat_case m).intro.
436 simplify.unfold lt.apply le_n.
437 intros.apply (trans_lt ? (S O)).
438 unfold lt.apply le_n.
439 apply lt_SO_smallest_factor.unfold lt. apply le_S_S.
440 apply le_S_S.apply le_O_n.
441 qed.
442
443 theorem divides_smallest_factor_n : 
444 \forall n:nat. O < n \to smallest_factor n \divides n.
445 intro.
446 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O O H).
447 intro.apply (nat_case m).intro. simplify.
448 apply (witness ? ? (S O)). simplify.reflexivity.
449 intros.
450 apply divides_b_true_to_divides.
451 change with 
452 (eqb ((S(S m1)) \mod (min_aux m1 (S (S O)) 
453   (\lambda m.(eqb ((S(S m1)) \mod m) O)))) O = true).
454 apply f_min_aux_true.
455 apply (ex_intro nat ? (S(S m1))).
456 split.split.
457 apply (le_S_S_to_le (S (S O)) (S (S m1)) ?).
458 apply (minus_le_O_to_le (S (S (S O))) (S (S (S m1))) ?).
459 apply (le_n O).
460 rewrite < sym_plus. simplify. apply le_n.
461 apply (eq_to_eqb_true (mod (S (S m1)) (S (S m1))) O ?).
462 apply (mod_n_n (S (S m1)) ?).
463 apply (H).
464 qed.
465   
466 theorem le_smallest_factor_n : 
467 \forall n:nat. smallest_factor n \le n.
468 intro.apply (nat_case n).simplify.apply le_n.
469 intro.apply (nat_case m).simplify.apply le_n.
470 intro.apply divides_to_le.
471 unfold lt.apply le_S_S.apply le_O_n.
472 apply divides_smallest_factor_n.
473 unfold lt.apply le_S_S.apply le_O_n.
474 qed.
475
476 theorem lt_smallest_factor_to_not_divides: \forall n,i:nat. 
477 (S O) < n \to (S O) < i \to i < (smallest_factor n) \to i \ndivides n.
478 intros 2.
479 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O (S O) H).
480 intro.apply (nat_case m).intro. apply False_ind.apply (not_le_Sn_n (S O) H).
481 intros.
482 apply divides_b_false_to_not_divides.
483 apply (lt_min_aux_to_false 
484 (\lambda i:nat.eqb ((S(S m1)) \mod i) O) (S (S O)) m1 i).
485 assumption.
486 assumption.
487 qed.
488
489 theorem prime_smallest_factor_n : 
490 \forall n:nat. (S O) < n \to prime (smallest_factor n).
491 intro.change with ((S(S O)) \le n \to (S O) < (smallest_factor n) \land 
492 (\forall m:nat. m \divides smallest_factor n \to (S O) < m \to  m = (smallest_factor n))).
493 intro.split.
494 apply lt_SO_smallest_factor.assumption.
495 intros.
496 cut (le m (smallest_factor n)).
497 elim (le_to_or_lt_eq m (smallest_factor n) Hcut).
498 absurd (m \divides n).
499 apply (transitive_divides m (smallest_factor n)).
500 assumption.
501 apply divides_smallest_factor_n.
502 apply (trans_lt ? (S O)). unfold lt. apply le_n. exact H.
503 apply lt_smallest_factor_to_not_divides.
504 exact H.assumption.assumption.assumption.
505 apply divides_to_le.
506 apply (trans_lt O (S O)).
507 apply (le_n (S O)).
508 apply lt_SO_smallest_factor.
509 exact H.
510 assumption.
511 qed.
512
513 theorem prime_to_smallest_factor: \forall n. prime n \to
514 smallest_factor n = n.
515 intro.apply (nat_case n).intro.apply False_ind.apply (not_prime_O H).
516 intro.apply (nat_case m).intro.apply False_ind.apply (not_prime_SO H).
517 intro.
518 change with 
519 ((S O) < (S(S m1)) \land 
520 (\forall m:nat. m \divides S(S m1) \to (S O) < m \to  m = (S(S m1))) \to 
521 smallest_factor (S(S m1)) = (S(S m1))).
522 intro.elim H.apply H2.
523 apply divides_smallest_factor_n.
524 apply (trans_lt ? (S O)).unfold lt. apply le_n.assumption.
525 apply lt_SO_smallest_factor.
526 assumption.
527 qed.
528
529 (* a number n > O is prime iff its smallest factor is n *)
530 definition primeb \def \lambda n:nat.
531 match n with
532 [ O \Rightarrow false
533 | (S p) \Rightarrow
534   match p with
535   [ O \Rightarrow false
536   | (S q) \Rightarrow eqb (smallest_factor (S(S q))) (S(S q))]].
537
538 (* it works! 
539 theorem example4 : primeb (S(S(S O))) = true.
540 normalize.reflexivity.
541 qed.
542
543 theorem example5 : primeb (S(S(S(S(S(S O)))))) = false.
544 normalize.reflexivity.
545 qed.
546
547 theorem example6 : primeb (S(S(S(S((S(S(S(S(S(S(S O)))))))))))) = true.
548 normalize.reflexivity.
549 qed.
550
551 theorem example7 : primeb (S(S(S(S(S(S((S(S(S(S((S(S(S(S(S(S(S O))))))))))))))))))) = true.
552 normalize.reflexivity.
553 qed. *)
554
555 theorem primeb_to_Prop: \forall n.
556 match primeb n with
557 [ true \Rightarrow prime n
558 | false \Rightarrow \lnot (prime n)].
559 intro.
560 apply (nat_case n).simplify.unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_O (S O) H1).
561 intro.apply (nat_case m).simplify.unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_n (S O) H1).
562 intro.
563 change with 
564 match eqb (smallest_factor (S(S m1))) (S(S m1)) with
565 [ true \Rightarrow prime (S(S m1))
566 | false \Rightarrow \lnot (prime (S(S m1)))].
567 apply (eqb_elim (smallest_factor (S(S m1))) (S(S m1))).
568 intro.simplify.
569 rewrite < H.
570 apply prime_smallest_factor_n.
571 unfold lt.apply le_S_S.apply le_S_S.apply le_O_n.
572 intro.simplify.
573 change with (prime (S(S m1)) \to False).
574 intro.apply H.
575 apply prime_to_smallest_factor.
576 assumption.
577 qed.
578
579 theorem primeb_true_to_prime : \forall n:nat.
580 primeb n = true \to prime n.
581 intros.change with
582 match true with 
583 [ true \Rightarrow prime n
584 | false \Rightarrow \lnot (prime n)].
585 rewrite < H.
586 apply primeb_to_Prop.
587 qed.
588
589 theorem primeb_false_to_not_prime : \forall n:nat.
590 primeb n = false \to \lnot (prime n).
591 intros.change with
592 match false with 
593 [ true \Rightarrow prime n
594 | false \Rightarrow \lnot (prime n)].
595 rewrite < H.
596 apply primeb_to_Prop.
597 qed.
598
599 theorem decidable_prime : \forall n:nat.decidable (prime n).
600 intro.unfold decidable.
601 cut 
602 (match primeb n with
603 [ true \Rightarrow prime n
604 | false \Rightarrow \lnot (prime n)] \to (prime n) \lor \lnot (prime n)).
605 apply Hcut.apply primeb_to_Prop.
606 elim (primeb n).left.apply H.right.apply H.
607 qed.
608
609 theorem prime_to_primeb_true: \forall n:nat. 
610 prime n \to primeb n = true.
611 intros.
612 cut (match (primeb n) with
613 [ true \Rightarrow prime n
614 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = true)).
615 apply Hcut.apply primeb_to_Prop.
616 elim (primeb n).reflexivity.
617 absurd (prime n).assumption.assumption.
618 qed.
619
620 theorem not_prime_to_primeb_false: \forall n:nat. 
621 \lnot(prime n) \to primeb n = false.
622 intros.
623 cut (match (primeb n) with
624 [ true \Rightarrow prime n
625 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = false)).
626 apply Hcut.apply primeb_to_Prop.
627 elim (primeb n).
628 absurd (prime n).assumption.assumption.
629 reflexivity.
630 qed.
631