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.
47 apply (witness n m p).
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).
130 apply (witness p O O).
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).
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.
159 apply (nat_case1 n).intro.
160 rewrite > H2.rewrite > H3.rewrite > H5.
161 rewrite < times_n_O.reflexivity.
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.
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.
176 elim (le_to_or_lt_eq O n2).
178 absurd (O<m).assumption.
179 rewrite > H2.rewrite < H3.rewrite < times_n_O.
180 apply (not_le_Sn_n O).
184 theorem divides_to_lt_O : \forall n,m. O < m \to n \divides m \to O < n.
186 elim (le_to_or_lt_eq O n (le_O_n n)).
188 rewrite < H3.absurd (O < m).assumption.
189 rewrite > H2.rewrite < H3.
190 simplify.exact (not_le_Sn_n O).
193 (*a variant of or_div_mod *)
194 theorem or_div_mod1: \forall n,q. O < q \to
195 (divides q (S n)) \land S n = (S (div n q)) * q \lor
196 (\lnot (divides q (S n)) \land S n= (div n q) * q + S (n\mod q)).
197 intros.elim (or_div_mod n q H);elim H1
199 [apply (witness ? ? (S (n/q))).
200 rewrite > sym_times.assumption
205 apply (not_eq_O_S (n \mod q)).
206 (* come faccio a fare unfold nelleipotesi ? *)
207 cut ((S n) \mod q = O)
209 apply (div_mod_spec_to_eq2 (S n) q (div (S n) q) (mod (S n) q) (div n q) (S (mod n q)))
210 [apply div_mod_spec_div_mod.
212 |apply div_mod_spec_intro;assumption
214 |apply divides_to_mod_O;assumption
221 theorem divides_to_div: \forall n,m.divides n m \to m/n*n = m.
223 elim (le_to_or_lt_eq O n (le_O_n n))
225 rewrite < (divides_to_mod_O ? ? H H1).
230 generalize in match H2.
239 theorem divides_div: \forall d,n. divides d n \to divides (n/d) n.
241 apply (witness ? ? d).
243 apply divides_to_div.
247 theorem div_div: \forall n,d:nat. O < n \to divides d n \to
250 apply (inj_times_l1 (n/d))
251 [apply (lt_times_n_to_lt d)
252 [apply (divides_to_lt_O ? ? H H1).
253 |rewrite > divides_to_div;assumption
255 |rewrite > divides_to_div
256 [rewrite > sym_times.
257 rewrite > divides_to_div
261 |apply (witness ? ? d).
263 apply divides_to_div.
269 theorem divides_to_eq_times_div_div_times: \forall a,b,c:nat.
270 O \lt b \to c \divides b \to a * (b /c) = (a*b)/c.
274 rewrite > (sym_times c n2).
276 [ rewrite > (lt_O_to_div_times n2 c)
277 [ rewrite < assoc_times.
278 rewrite > (lt_O_to_div_times (a *n2) c)
284 | apply (divides_to_lt_O c b);
289 theorem eq_div_plus: \forall n,m,d. O < d \to
290 divides d n \to divides d m \to
291 (n + m ) / d = n/d + m/d.
295 rewrite > H3.rewrite > H4.
296 rewrite < distr_times_plus.
298 rewrite > sym_times in ⊢ (? ? ? (? (? % ?) ?)).
299 rewrite > sym_times in ⊢ (? ? ? (? ? (? % ?))).
300 rewrite > lt_O_to_div_times
301 [rewrite > lt_O_to_div_times
302 [rewrite > lt_O_to_div_times
312 (* boolean divides *)
313 definition divides_b : nat \to nat \to bool \def
314 \lambda n,m :nat. (eqb (m \mod n) O).
316 theorem divides_b_to_Prop :
317 \forall n,m:nat. O < n \to
318 match divides_b n m with
319 [ true \Rightarrow n \divides m
320 | false \Rightarrow n \ndivides m].
321 intros.unfold divides_b.
323 intro.simplify.apply mod_O_to_divides.assumption.assumption.
324 intro.simplify.unfold Not.intro.apply H1.apply divides_to_mod_O.assumption.assumption.
327 theorem divides_b_true_to_divides1:
328 \forall n,m:nat. O < n \to
329 (divides_b n m = true ) \to n \divides m.
333 [ true \Rightarrow n \divides m
334 | false \Rightarrow n \ndivides m].
335 rewrite < H1.apply divides_b_to_Prop.
339 theorem divides_b_true_to_divides:
340 \forall n,m:nat. divides_b n m = true \to n \divides m.
341 intros 2.apply (nat_case n)
343 [intro.apply divides_n_n
344 |simplify.intros.apply False_ind.
345 apply not_eq_true_false.apply sym_eq.
349 apply divides_b_true_to_divides1
350 [apply lt_O_S|assumption]
354 theorem divides_b_false_to_not_divides1:
355 \forall n,m:nat. O < n \to
356 (divides_b n m = false ) \to n \ndivides m.
360 [ true \Rightarrow n \divides m
361 | false \Rightarrow n \ndivides m].
362 rewrite < H1.apply divides_b_to_Prop.
366 theorem divides_b_false_to_not_divides:
367 \forall n,m:nat. divides_b n m = false \to n \ndivides m.
368 intros 2.apply (nat_case n)
370 [simplify.unfold Not.intros.
371 apply not_eq_true_false.assumption
372 |unfold Not.intros.elim H1.
373 apply (not_eq_O_S m1).apply sym_eq.
377 apply divides_b_false_to_not_divides1
378 [apply lt_O_S|assumption]
382 theorem decidable_divides: \forall n,m:nat.O < n \to
383 decidable (n \divides m).
384 intros.unfold decidable.
386 (match divides_b n m with
387 [ true \Rightarrow n \divides m
388 | false \Rightarrow n \ndivides m] \to n \divides m \lor n \ndivides m).
389 apply Hcut.apply divides_b_to_Prop.assumption.
390 elim (divides_b n m).left.apply H1.right.apply H1.
393 theorem divides_to_divides_b_true : \forall n,m:nat. O < n \to
394 n \divides m \to divides_b n m = true.
396 cut (match (divides_b n m) with
397 [ true \Rightarrow n \divides m
398 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = true)).
399 apply Hcut.apply divides_b_to_Prop.assumption.
400 elim (divides_b n m).reflexivity.
401 absurd (n \divides m).assumption.assumption.
404 theorem divides_to_divides_b_true1 : \forall n,m:nat.
405 O < m \to n \divides m \to divides_b n m = true.
407 elim (le_to_or_lt_eq O n (le_O_n n))
408 [apply divides_to_divides_b_true
409 [assumption|assumption]
414 apply (not_le_Sn_O O).
420 theorem not_divides_to_divides_b_false: \forall n,m:nat. O < n \to
421 \lnot(n \divides m) \to (divides_b n m) = false.
423 cut (match (divides_b n m) with
424 [ true \Rightarrow n \divides m
425 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = false)).
426 apply Hcut.apply divides_b_to_Prop.assumption.
427 elim (divides_b n m).
428 absurd (n \divides m).assumption.assumption.
432 theorem divides_b_div_true:
433 \forall d,n. O < n \to
434 divides_b d n = true \to divides_b (n/d) n = true.
436 apply divides_to_divides_b_true1
439 apply divides_b_true_to_divides.
444 theorem divides_b_true_to_lt_O: \forall n,m. O < n \to divides_b m n = true \to O < m.
446 elim (le_to_or_lt_eq ? ? (le_O_n m))
452 apply (lt_to_not_eq O n H).
454 apply eqb_true_to_eq.
460 theorem divides_f_pi_f : \forall f:nat \to nat.\forall n,m,i:nat.
461 m \le i \to i \le n+m \to f i \divides pi n f m.
462 intros 5.elim n.simplify.
463 cut (i = m).rewrite < Hcut.apply divides_n_n.
464 apply antisymmetric_le.assumption.assumption.
466 cut (i < S n1+m \lor i = S n1 + m).
468 apply (transitive_divides ? (pi n1 f m)).
469 apply H1.apply le_S_S_to_le. assumption.
470 apply (witness ? ? (f (S n1+m))).apply sym_times.
472 apply (witness ? ? (pi n1 f m)).reflexivity.
473 apply le_to_or_lt_eq.assumption.
477 theorem mod_S_pi: \forall f:nat \to nat.\forall n,i:nat.
478 i < n \to (S O) < (f i) \to (S (pi n f)) \mod (f i) = (S O).
479 intros.cut (pi n f) \mod (f i) = O.
481 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
482 rewrite > Hcut.assumption.
483 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
484 apply divides_f_pi_f.assumption.
488 (* divides and fact *)
489 theorem divides_fact : \forall n,i:nat.
490 O < i \to i \le n \to i \divides n!.
491 intros 3.elim n.absurd (O<i).assumption.apply (le_n_O_elim i H1).
492 apply (not_le_Sn_O O).
493 change with (i \divides (S n1)*n1!).
494 apply (le_n_Sm_elim i n1 H2).
496 apply (transitive_divides ? n1!).
497 apply H1.apply le_S_S_to_le. assumption.
498 apply (witness ? ? (S n1)).apply sym_times.
501 apply (witness ? ? n1!).reflexivity.
504 theorem mod_S_fact: \forall n,i:nat.
505 (S O) < i \to i \le n \to (S n!) \mod i = (S O).
506 intros.cut (n! \mod i = O).
508 apply mod_S.apply (trans_lt O (S O)).apply (le_n (S O)).assumption.
509 rewrite > Hcut.assumption.
510 apply divides_to_mod_O.apply (trans_lt O (S O)).apply (le_n (S O)).assumption.
511 apply divides_fact.apply (trans_lt O (S O)).apply (le_n (S O)).assumption.
515 theorem not_divides_S_fact: \forall n,i:nat.
516 (S O) < i \to i \le n \to i \ndivides S n!.
518 apply divides_b_false_to_not_divides.
520 rewrite > mod_S_fact[simplify.reflexivity|assumption|assumption].
524 definition prime : nat \to Prop \def
525 \lambda n:nat. (S O) < n \land
526 (\forall m:nat. m \divides n \to (S O) < m \to m = n).
528 theorem not_prime_O: \lnot (prime O).
529 unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_O (S O) H1).
532 theorem not_prime_SO: \lnot (prime (S O)).
533 unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_n (S O) H1).
536 theorem prime_to_lt_O: \forall p. prime p \to O < p.
537 intros.elim H.apply lt_to_le.assumption.
540 theorem prime_to_lt_SO: \forall p. prime p \to S O < p.
545 (* smallest factor *)
546 definition smallest_factor : nat \to nat \def
552 [ O \Rightarrow (S O)
553 | (S q) \Rightarrow min_aux q (S (S O)) (\lambda m.(eqb ((S(S q)) \mod m) O))]].
556 theorem example1 : smallest_factor (S(S(S O))) = (S(S(S O))).
557 normalize.reflexivity.
560 theorem example2: smallest_factor (S(S(S(S O)))) = (S(S O)).
561 normalize.reflexivity.
564 theorem example3 : smallest_factor (S(S(S(S(S(S(S O))))))) = (S(S(S(S(S(S(S O))))))).
565 simplify.reflexivity.
568 theorem lt_SO_smallest_factor:
569 \forall n:nat. (S O) < n \to (S O) < (smallest_factor n).
571 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O (S O) H).
572 intro.apply (nat_case m).intro. apply False_ind.apply (not_le_Sn_n (S O) H).
575 (S O < min_aux m1 (S (S O)) (\lambda m.(eqb ((S(S m1)) \mod m) O))).
576 apply (lt_to_le_to_lt ? (S (S O))).
577 apply (le_n (S(S O))).
578 cut ((S(S O)) = (S(S m1)) - m1).
581 apply sym_eq.apply plus_to_minus.
582 rewrite < sym_plus.simplify.reflexivity.
585 theorem lt_O_smallest_factor: \forall n:nat. O < n \to O < (smallest_factor n).
587 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_n O H).
588 intro.apply (nat_case m).intro.
589 simplify.unfold lt.apply le_n.
590 intros.apply (trans_lt ? (S O)).
591 unfold lt.apply le_n.
592 apply lt_SO_smallest_factor.unfold lt. apply le_S_S.
593 apply le_S_S.apply le_O_n.
596 theorem divides_smallest_factor_n :
597 \forall n:nat. O < n \to smallest_factor n \divides n.
599 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O O H).
600 intro.apply (nat_case m).intro. simplify.
601 apply (witness ? ? (S O)). simplify.reflexivity.
603 apply divides_b_true_to_divides.
605 (eqb ((S(S m1)) \mod (min_aux m1 (S (S O))
606 (\lambda m.(eqb ((S(S m1)) \mod m) O)))) O = true).
607 apply f_min_aux_true.
608 apply (ex_intro nat ? (S(S m1))).
610 apply (le_S_S_to_le (S (S O)) (S (S m1)) ?).
611 apply (minus_le_O_to_le (S (S (S O))) (S (S (S m1))) ?).
613 rewrite < sym_plus. simplify. apply le_n.
614 apply (eq_to_eqb_true (mod (S (S m1)) (S (S m1))) O ?).
615 apply (mod_n_n (S (S m1)) ?).
619 theorem le_smallest_factor_n :
620 \forall n:nat. smallest_factor n \le n.
621 intro.apply (nat_case n).simplify.apply le_n.
622 intro.apply (nat_case m).simplify.apply le_n.
623 intro.apply divides_to_le.
624 unfold lt.apply le_S_S.apply le_O_n.
625 apply divides_smallest_factor_n.
626 unfold lt.apply le_S_S.apply le_O_n.
629 theorem lt_smallest_factor_to_not_divides: \forall n,i:nat.
630 (S O) < n \to (S O) < i \to i < (smallest_factor n) \to i \ndivides n.
632 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O (S O) H).
633 intro.apply (nat_case m).intro. apply False_ind.apply (not_le_Sn_n (S O) H).
635 apply divides_b_false_to_not_divides.
636 apply (lt_min_aux_to_false
637 (\lambda i:nat.eqb ((S(S m1)) \mod i) O) (S (S O)) m1 i).
642 theorem prime_smallest_factor_n :
643 \forall n:nat. (S O) < n \to prime (smallest_factor n).
644 intro.change with ((S(S O)) \le n \to (S O) < (smallest_factor n) \land
645 (\forall m:nat. m \divides smallest_factor n \to (S O) < m \to m = (smallest_factor n))).
647 apply lt_SO_smallest_factor.assumption.
649 cut (le m (smallest_factor n)).
650 elim (le_to_or_lt_eq m (smallest_factor n) Hcut).
651 absurd (m \divides n).
652 apply (transitive_divides m (smallest_factor n)).
654 apply divides_smallest_factor_n.
655 apply (trans_lt ? (S O)). unfold lt. apply le_n. exact H.
656 apply lt_smallest_factor_to_not_divides.
657 exact H.assumption.assumption.assumption.
659 apply (trans_lt O (S O)).
661 apply lt_SO_smallest_factor.
666 theorem prime_to_smallest_factor: \forall n. prime n \to
667 smallest_factor n = n.
668 intro.apply (nat_case n).intro.apply False_ind.apply (not_prime_O H).
669 intro.apply (nat_case m).intro.apply False_ind.apply (not_prime_SO H).
672 ((S O) < (S(S m1)) \land
673 (\forall m:nat. m \divides S(S m1) \to (S O) < m \to m = (S(S m1))) \to
674 smallest_factor (S(S m1)) = (S(S m1))).
675 intro.elim H.apply H2.
676 apply divides_smallest_factor_n.
677 apply (trans_lt ? (S O)).unfold lt. apply le_n.assumption.
678 apply lt_SO_smallest_factor.
682 (* a number n > O is prime iff its smallest factor is n *)
683 definition primeb \def \lambda n:nat.
685 [ O \Rightarrow false
688 [ O \Rightarrow false
689 | (S q) \Rightarrow eqb (smallest_factor (S(S q))) (S(S q))]].
692 theorem example4 : primeb (S(S(S O))) = true.
693 normalize.reflexivity.
696 theorem example5 : primeb (S(S(S(S(S(S O)))))) = false.
697 normalize.reflexivity.
700 theorem example6 : primeb (S(S(S(S((S(S(S(S(S(S(S O)))))))))))) = true.
701 normalize.reflexivity.
704 theorem example7 : primeb (S(S(S(S(S(S((S(S(S(S((S(S(S(S(S(S(S O))))))))))))))))))) = true.
705 normalize.reflexivity.
708 theorem primeb_to_Prop: \forall n.
710 [ true \Rightarrow prime n
711 | false \Rightarrow \lnot (prime n)].
713 apply (nat_case n).simplify.unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_O (S O) H1).
714 intro.apply (nat_case m).simplify.unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_n (S O) H1).
717 match eqb (smallest_factor (S(S m1))) (S(S m1)) with
718 [ true \Rightarrow prime (S(S m1))
719 | false \Rightarrow \lnot (prime (S(S m1)))].
720 apply (eqb_elim (smallest_factor (S(S m1))) (S(S m1))).
723 apply prime_smallest_factor_n.
724 unfold lt.apply le_S_S.apply le_S_S.apply le_O_n.
726 change with (prime (S(S m1)) \to False).
728 apply prime_to_smallest_factor.
732 theorem primeb_true_to_prime : \forall n:nat.
733 primeb n = true \to prime n.
736 [ true \Rightarrow prime n
737 | false \Rightarrow \lnot (prime n)].
739 apply primeb_to_Prop.
742 theorem primeb_false_to_not_prime : \forall n:nat.
743 primeb n = false \to \lnot (prime n).
746 [ true \Rightarrow prime n
747 | false \Rightarrow \lnot (prime n)].
749 apply primeb_to_Prop.
752 theorem decidable_prime : \forall n:nat.decidable (prime n).
753 intro.unfold decidable.
756 [ true \Rightarrow prime n
757 | false \Rightarrow \lnot (prime n)] \to (prime n) \lor \lnot (prime n)).
758 apply Hcut.apply primeb_to_Prop.
759 elim (primeb n).left.apply H.right.apply H.
762 theorem prime_to_primeb_true: \forall n:nat.
763 prime n \to primeb n = true.
765 cut (match (primeb n) with
766 [ true \Rightarrow prime n
767 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = true)).
768 apply Hcut.apply primeb_to_Prop.
769 elim (primeb n).reflexivity.
770 absurd (prime n).assumption.assumption.
773 theorem not_prime_to_primeb_false: \forall n:nat.
774 \lnot(prime n) \to primeb n = false.
776 cut (match (primeb n) with
777 [ true \Rightarrow prime n
778 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = false)).
779 apply Hcut.apply primeb_to_Prop.
781 absurd (prime n).assumption.assumption.