helm/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 simplify.
  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 (* divides le *)
 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.
 158 apply le_plus_n.
 159 elim le_to_or_lt_eq O n2.
 160 assumption.
 161 absurd O<m.assumption.
 162 rewrite > H2.rewrite < H3.rewrite < times_n_O.
 163 apply not_le_Sn_n O.
 164 apply le_O_n.
 165 qed.
 166
 167 theorem divides_to_lt_O : \forall n,m. O < m \to n \divides m \to O < n.
 168 intros.elim H1.
 169 elim le_to_or_lt_eq O n (le_O_n n).
 170 assumption.
 171 rewrite < H3.absurd O < m.assumption.
 172 rewrite > H2.rewrite < H3.
 173 simplify.exact not_le_Sn_n O.
 174 qed.
 175
 176 (* boolean divides *)
 177 definition divides_b : nat \to nat \to bool \def
 178 \lambda n,m :nat. (eqb (m \mod n) O).
 179
 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].
 185 intros.
 186 change with
 187 match eqb (m \mod n) O with
 188 [ true \Rightarrow n \divides m
 189 | false \Rightarrow n \ndivides m].
 190 apply eqb_elim.
 191 intro.simplify.apply mod_O_to_divides.assumption.assumption.
 192 intro.simplify.intro.apply H1.apply divides_to_mod_O.assumption.assumption.
 193 qed.
 194
 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.
 198 intros.
 199 change with
 200 match true with
 201 [ true \Rightarrow n \divides m
 202 | false \Rightarrow n \ndivides m].
 203 rewrite < H1.apply divides_b_to_Prop.
 204 assumption.
 205 qed.
 206
 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.
 210 intros.
 211 change with
 212 match false with
 213 [ true \Rightarrow n \divides m
 214 | false \Rightarrow n \ndivides m].
 215 rewrite < H1.apply divides_b_to_Prop.
 216 assumption.
 217 qed.
 218
 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.
 222 cut
 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.
 228 qed.
 229
 230 theorem divides_to_divides_b_true : \forall n,m:nat. O < n \to
 231 n \divides m \to divides_b n m = true.
 232 intros.
 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.
 239 qed.
 240
 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.
 243 intros.
 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.
 248 elim divides_b n m.
 249 absurd (n \divides m).assumption.assumption.
 250 reflexivity.
 251 qed.
 252
 253 (* divides and pi *)
 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.
 259 simplify.
 260 cut i < S n1+m \lor i = S n1 + m.
 261 elim Hcut.
 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.
 265 rewrite > H3.
 266 apply witness ? ? (pi n1 f m).reflexivity.
 267 apply le_to_or_lt_eq.assumption.
 268 qed.
 269
 270 (*
 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.
 274 rewrite < Hcut.
 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.
 279 qed.
 280 *)
 281
 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.
 286 apply not_le_Sn_O O.
 287 change with i \divides (S n1)*n1!.
 288 apply le_n_Sm_elim i n1 H2.
 289 intro.
 290 apply transitive_divides ? n1!.
 291 apply H1.apply le_S_S_to_le. assumption.
 292 apply witness ? ? (S n1).apply sym_times.
 293 intro.
 294 rewrite > H3.
 295 apply witness ? ? n1!.reflexivity.
 296 qed.
 297
 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.
 301 rewrite < Hcut.
 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.
 306 assumption.
 307 qed.
 308
 309 theorem not_divides_S_fact: \forall n,i:nat.
 310 (S O) < i \to i \le n \to i \ndivides S n!.
 311 intros.
 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.
 317 qed.
 318
 319 (* prime *)
 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).
 323
 324 theorem not_prime_O: \lnot (prime O).
 325 simplify.intro.elim H.apply not_le_Sn_O (S O) H1.
 326 qed.
 327
 328 theorem not_prime_SO: \lnot (prime (S O)).
 329 simplify.intro.elim H.apply not_le_Sn_n (S O) H1.
 330 qed.
 331
 332 (* smallest factor *)
 333 definition smallest_factor : nat \to nat \def
 334 \lambda n:nat.
 335 match n with
 336 [ O \Rightarrow O
 337 | (S p) \Rightarrow
 338   match p with
 339   [ O \Rightarrow (S O)
 340   | (S q) \Rightarrow min_aux q (S(S q)) (\lambda m.(eqb ((S(S q)) \mod m) O))]].
 341
 342 (* it works !
 343 theorem example1 : smallest_prime_factor (S(S(S O))) = (S(S(S O))).
 344 normalize.reflexivity.
 345 qed.
 346
 347 theorem example2: smallest_prime_factor (S(S(S(S O)))) = (S(S O)).
 348 normalize.reflexivity.
 349 qed.
 350
 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.
 353 qed. *)
 354
 355 theorem lt_SO_smallest_factor:
 356 \forall n:nat. (S O) < n \to (S O) < (smallest_factor n).
 357 intro.
 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.
 360 intros.
 361 change with
 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)).
 364 apply le_n (S(S O)).
 365 cut (S(S O)) = (S(S m1)) - m1.
 366 rewrite > Hcut.
 367 apply le_min_aux.
 368 apply sym_eq.apply plus_to_minus.
 369 rewrite < sym_plus.simplify.reflexivity.
 370 qed.
 371
 372 theorem lt_O_smallest_factor: \forall n:nat. O < n \to O < (smallest_factor n).
 373 intro.
 374 apply nat_case n.intro.apply False_ind.apply not_le_Sn_n O H.
 375 intro.apply nat_case m.intro.
 376 simplify.apply le_n.
 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.
 381 qed.
 382
 383 theorem divides_smallest_factor_n :
 384 \forall n:nat. O < n \to smallest_factor n \divides n.
 385 intro.
 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.
 389 intros.
 390 apply divides_b_true_to_divides.
 391 apply lt_O_smallest_factor ? H.
 392 change with
 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)).
 397 split.split.
 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.
 402 qed.
 403
 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.
 412 qed.
 413
 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.
 416 intros 2.
 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.
 419 intros.
 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.
 429 exact H2.
 430 qed.
 431
 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)).
 436 intro.split.
 437 apply lt_SO_smallest_factor.assumption.
 438 intros.
 439 cut le m (smallest_factor n).
 440 elim le_to_or_lt_eq m (smallest_factor n) Hcut.
 441 absurd m \divides n.
 442 apply transitive_divides m (smallest_factor n).
 443 assumption.
 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.
 448 apply divides_to_le.
 449 apply trans_lt O (S O).
 450 apply le_n (S O).
 451 apply lt_SO_smallest_factor.
 452 exact H.
 453 assumption.
 454 qed.
 455
 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.
 460 intro.
 461 change with
 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.
 469 assumption.
 470 qed.
 471
 472 (* a number n > O is prime iff its smallest factor is n *)
 473 definition primeb \def \lambda n:nat.
 474 match n with
 475 [ O \Rightarrow false
 476 | (S p) \Rightarrow
 477   match p with
 478   [ O \Rightarrow false
 479   | (S q) \Rightarrow eqb (smallest_factor (S(S q))) (S(S q))]].
 480
 481 (* it works!
 482 theorem example4 : primeb (S(S(S O))) = true.
 483 normalize.reflexivity.
 484 qed.
 485
 486 theorem example5 : primeb (S(S(S(S(S(S O)))))) = false.
 487 normalize.reflexivity.
 488 qed.
 489
 490 theorem example6 : primeb (S(S(S(S((S(S(S(S(S(S(S O)))))))))))) = true.
 491 normalize.reflexivity.
 492 qed.
 493
 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.
 496 qed. *)
 497
 498 theorem primeb_to_Prop: \forall n.
 499 match primeb n with
 500 [ true \Rightarrow prime n
 501 | false \Rightarrow \lnot (prime n)].
 502 intro.
 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.
 505 intro.
 506 change with
 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)).
 512 rewrite < H.
 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.
 517 intro.apply H.
 518 apply prime_to_smallest_factor.
 519 assumption.
 520 qed.
 521
 522 theorem primeb_true_to_prime : \forall n:nat.
 523 primeb n = true \to prime n.
 524 intros.change with
 525 match true with
 526 [ true \Rightarrow prime n
 527 | false \Rightarrow \lnot (prime n)].
 528 rewrite < H.
 529 apply primeb_to_Prop.
 530 qed.
 531
 532 theorem primeb_false_to_not_prime : \forall n:nat.
 533 primeb n = false \to \lnot (prime n).
 534 intros.change with
 535 match false with
 536 [ true \Rightarrow prime n
 537 | false \Rightarrow \lnot (prime n)].
 538 rewrite < H.
 539 apply primeb_to_Prop.
 540 qed.
 541
 542 theorem decidable_prime : \forall n:nat.decidable (prime n).
 543 intro.change with (prime n) \lor \lnot (prime n).
 544 cut
 545 match primeb n with
 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.
 550 qed.
 551
 552 theorem prime_to_primeb_true: \forall n:nat.
 553 prime n \to primeb n = true.
 554 intros.
 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.
 561 qed.
 562
 563 theorem not_prime_to_primeb_false: \forall n:nat.
 564 \lnot(prime n) \to primeb n = false.
 565 intros.
 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.
 570 elim primeb n.
 571 absurd (prime n).assumption.assumption.
 572 reflexivity.
 573 qed.
 574