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 (*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
 198   [left.split
 199     [apply (witness ? ? (S (n/q))).
 200      rewrite > sym_times.assumption
 201     |assumption
 202     ]
 203   |right.split
 204     [intro.
 205      apply (not_eq_O_S (n \mod q)).
 206      (* come faccio a fare unfold nelleipotesi ? *)
 207      cut ((S n) \mod q = O)
 208       [rewrite < Hcut.
 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.
 211          assumption
 212         |apply div_mod_spec_intro;assumption
 213         ]
 214       |apply divides_to_mod_O;assumption
 215       ]
 216     |assumption
 217     ]
 218   ]
 219 qed.
 220
 221 theorem divides_to_div: \forall n,m.divides n m \to m/n*n = m.
 222 intro.
 223 elim (le_to_or_lt_eq O n (le_O_n n))
 224   [rewrite > plus_n_O.
 225    rewrite < (divides_to_mod_O ? ? H H1).
 226    apply sym_eq.
 227    apply div_mod.
 228    assumption
 229   |elim H1.
 230    generalize in match H2.
 231    rewrite < H.
 232    simplify.
 233    intro.
 234    rewrite > H3.
 235    reflexivity
 236   ]
 237 qed.
 238
 239 theorem divides_div: \forall d,n. divides d n \to divides (n/d) n.
 240 intros.
 241 apply (witness ? ? d).
 242 apply sym_eq.
 243 apply divides_to_div.
 244 assumption.
 245 qed.
 246
 247 theorem div_div: \forall n,d:nat. O < n \to divides d n \to
 248 n/(n/d) = d.
 249 intros.
 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
 254     ]
 255   |rewrite > divides_to_div
 256     [rewrite > sym_times.
 257      rewrite > divides_to_div
 258       [reflexivity
 259       |assumption
 260       ]
 261     |apply (witness ? ? d).
 262      apply sym_eq.
 263      apply divides_to_div.
 264      assumption
 265     ]
 266   ]
 267 qed.
 268
 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.
 271 intros.
 272 elim H1.
 273 rewrite > H2.
 274 rewrite > (sym_times c n2).
 275 cut(O \lt c)
 276 [ rewrite > (lt_O_to_div_times n2 c)
 277   [ rewrite < assoc_times.
 278     rewrite > (lt_O_to_div_times (a *n2) c)
 279     [ reflexivity
 280     | assumption
 281     ]
 282   | assumption
 283   ]
 284 | apply (divides_to_lt_O c b);
 285     assumption.
 286 ]
 287 qed.
 288
 289
 290 (* boolean divides *)
 291 definition divides_b : nat \to nat \to bool \def
 292 \lambda n,m :nat. (eqb (m \mod n) O).
 293
 294 theorem divides_b_to_Prop :
 295 \forall n,m:nat. O < n \to
 296 match divides_b n m with
 297 [ true \Rightarrow n \divides m
 298 | false \Rightarrow n \ndivides m].
 299 intros.unfold divides_b.
 300 apply eqb_elim.
 301 intro.simplify.apply mod_O_to_divides.assumption.assumption.
 302 intro.simplify.unfold Not.intro.apply H1.apply divides_to_mod_O.assumption.assumption.
 303 qed.
 304
 305 theorem divides_b_true_to_divides1:
 306 \forall n,m:nat. O < n \to
 307 (divides_b n m = true ) \to n \divides m.
 308 intros.
 309 change with
 310 match true with
 311 [ true \Rightarrow n \divides m
 312 | false \Rightarrow n \ndivides m].
 313 rewrite < H1.apply divides_b_to_Prop.
 314 assumption.
 315 qed.
 316
 317 theorem divides_b_true_to_divides:
 318 \forall n,m:nat. divides_b n m = true \to n \divides m.
 319 intros 2.apply (nat_case n)
 320   [apply (nat_case m)
 321     [intro.apply divides_n_n
 322     |simplify.intros.apply False_ind.
 323      apply not_eq_true_false.apply sym_eq.
 324      assumption
 325     ]
 326   |intros.
 327    apply divides_b_true_to_divides1
 328     [apply lt_O_S|assumption]
 329   ]
 330 qed.
 331
 332 theorem divides_b_false_to_not_divides1:
 333 \forall n,m:nat. O < n \to
 334 (divides_b n m = false ) \to n \ndivides m.
 335 intros.
 336 change with
 337 match false with
 338 [ true \Rightarrow n \divides m
 339 | false \Rightarrow n \ndivides m].
 340 rewrite < H1.apply divides_b_to_Prop.
 341 assumption.
 342 qed.
 343
 344 theorem divides_b_false_to_not_divides:
 345 \forall n,m:nat. divides_b n m = false \to n \ndivides m.
 346 intros 2.apply (nat_case n)
 347   [apply (nat_case m)
 348     [simplify.unfold Not.intros.
 349      apply not_eq_true_false.assumption
 350     |unfold Not.intros.elim H1.
 351      apply (not_eq_O_S m1).apply sym_eq.
 352      assumption
 353     ]
 354   |intros.
 355    apply divides_b_false_to_not_divides1
 356     [apply lt_O_S|assumption]
 357   ]
 358 qed.
 359
 360 theorem decidable_divides: \forall n,m:nat.O < n \to
 361 decidable (n \divides m).
 362 intros.unfold decidable.
 363 cut
 364 (match divides_b n m with
 365 [ true \Rightarrow n \divides m
 366 | false \Rightarrow n \ndivides m] \to n \divides m \lor n \ndivides m).
 367 apply Hcut.apply divides_b_to_Prop.assumption.
 368 elim (divides_b n m).left.apply H1.right.apply H1.
 369 qed.
 370
 371 theorem divides_to_divides_b_true : \forall n,m:nat. O < n \to
 372 n \divides m \to divides_b n m = true.
 373 intros.
 374 cut (match (divides_b n m) with
 375 [ true \Rightarrow n \divides m
 376 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = true)).
 377 apply Hcut.apply divides_b_to_Prop.assumption.
 378 elim (divides_b n m).reflexivity.
 379 absurd (n \divides m).assumption.assumption.
 380 qed.
 381
 382 theorem divides_to_divides_b_true1 : \forall n,m:nat.
 383 O < m \to n \divides m \to divides_b n m = true.
 384 intro.
 385 elim (le_to_or_lt_eq O n (le_O_n n))
 386   [apply divides_to_divides_b_true
 387     [assumption|assumption]
 388   |apply False_ind.
 389    rewrite < H in H2.
 390    elim H2.
 391    simplify in H3.
 392    apply (not_le_Sn_O O).
 393    rewrite > H3 in H1.
 394    assumption
 395   ]
 396 qed.
 397
 398 theorem not_divides_to_divides_b_false: \forall n,m:nat. O < n \to
 399 \lnot(n \divides m) \to (divides_b n m) = false.
 400 intros.
 401 cut (match (divides_b n m) with
 402 [ true \Rightarrow n \divides m
 403 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = false)).
 404 apply Hcut.apply divides_b_to_Prop.assumption.
 405 elim (divides_b n m).
 406 absurd (n \divides m).assumption.assumption.
 407 reflexivity.
 408 qed.
 409
 410 theorem divides_b_div_true:
 411 \forall d,n. O < n \to
 412   divides_b d n = true \to divides_b (n/d) n = true.
 413 intros.
 414 apply divides_to_divides_b_true1
 415   [assumption
 416   |apply divides_div.
 417    apply divides_b_true_to_divides.
 418    assumption
 419   ]
 420 qed.
 421
 422 theorem divides_b_true_to_lt_O: \forall n,m. O < n \to divides_b m n = true \to O < m.
 423 intros.
 424 elim (le_to_or_lt_eq ? ? (le_O_n m))
 425   [assumption
 426   |apply False_ind.
 427    elim H1.
 428    rewrite < H2 in H1.
 429    simplify in H1.
 430    apply (lt_to_not_eq O n H).
 431    apply sym_eq.
 432    apply eqb_true_to_eq.
 433    assumption
 434   ]
 435 qed.
 436
 437 (* divides and pi *)
 438 theorem divides_f_pi_f : \forall f:nat \to nat.\forall n,m,i:nat.
 439 m \le i \to i \le n+m \to f i \divides pi n f m.
 440 intros 5.elim n.simplify.
 441 cut (i = m).rewrite < Hcut.apply divides_n_n.
 442 apply antisymmetric_le.assumption.assumption.
 443 simplify.
 444 cut (i < S n1+m \lor i = S n1 + m).
 445 elim Hcut.
 446 apply (transitive_divides ? (pi n1 f m)).
 447 apply H1.apply le_S_S_to_le. assumption.
 448 apply (witness ? ? (f (S n1+m))).apply sym_times.
 449 rewrite > H3.
 450 apply (witness ? ? (pi n1 f m)).reflexivity.
 451 apply le_to_or_lt_eq.assumption.
 452 qed.
 453
 454 (*
 455 theorem mod_S_pi: \forall f:nat \to nat.\forall n,i:nat.
 456 i < n \to (S O) < (f i) \to (S (pi n f)) \mod (f i) = (S O).
 457 intros.cut (pi n f) \mod (f i) = O.
 458 rewrite < Hcut.
 459 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
 460 rewrite > Hcut.assumption.
 461 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
 462 apply divides_f_pi_f.assumption.
 463 qed.
 464 *)
 465
 466 (* divides and fact *)
 467 theorem divides_fact : \forall n,i:nat.
 468 O < i \to i \le n \to i \divides n!.
 469 intros 3.elim n.absurd (O<i).assumption.apply (le_n_O_elim i H1).
 470 apply (not_le_Sn_O O).
 471 change with (i \divides (S n1)*n1!).
 472 apply (le_n_Sm_elim i n1 H2).
 473 intro.
 474 apply (transitive_divides ? n1!).
 475 apply H1.apply le_S_S_to_le. assumption.
 476 apply (witness ? ? (S n1)).apply sym_times.
 477 intro.
 478 rewrite > H3.
 479 apply (witness ? ? n1!).reflexivity.
 480 qed.
 481
 482 theorem mod_S_fact: \forall n,i:nat.
 483 (S O) < i \to i \le n \to (S n!) \mod i = (S O).
 484 intros.cut (n! \mod i = O).
 485 rewrite < Hcut.
 486 apply mod_S.apply (trans_lt O (S O)).apply (le_n (S O)).assumption.
 487 rewrite > Hcut.assumption.
 488 apply divides_to_mod_O.apply (trans_lt O (S O)).apply (le_n (S O)).assumption.
 489 apply divides_fact.apply (trans_lt O (S O)).apply (le_n (S O)).assumption.
 490 assumption.
 491 qed.
 492
 493 theorem not_divides_S_fact: \forall n,i:nat.
 494 (S O) < i \to i \le n \to i \ndivides S n!.
 495 intros.
 496 apply divides_b_false_to_not_divides.
 497 unfold divides_b.
 498 rewrite > mod_S_fact[simplify.reflexivity|assumption|assumption].
 499 qed.
 500
 501 (* prime *)
 502 definition prime : nat \to  Prop \def
 503 \lambda n:nat. (S O) < n \land
 504 (\forall m:nat. m \divides n \to (S O) < m \to  m = n).
 505
 506 theorem not_prime_O: \lnot (prime O).
 507 unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_O (S O) H1).
 508 qed.
 509
 510 theorem not_prime_SO: \lnot (prime (S O)).
 511 unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_n (S O) H1).
 512 qed.
 513
 514 theorem prime_to_lt_O: \forall p. prime p \to O < p.
 515 intros.elim H.apply lt_to_le.assumption.
 516 qed.
 517
 518 theorem prime_to_lt_SO: \forall p. prime p \to S O < p.
 519 intros.elim H.
 520 assumption.
 521 qed.
 522
 523 (* smallest factor *)
 524 definition smallest_factor : nat \to nat \def
 525 \lambda n:nat.
 526 match n with
 527 [ O \Rightarrow O
 528 | (S p) \Rightarrow
 529   match p with
 530   [ O \Rightarrow (S O)
 531   | (S q) \Rightarrow min_aux q (S (S O)) (\lambda m.(eqb ((S(S q)) \mod m) O))]].
 532
 533 (* it works !
 534 theorem example1 : smallest_factor (S(S(S O))) = (S(S(S O))).
 535 normalize.reflexivity.
 536 qed.
 537
 538 theorem example2: smallest_factor (S(S(S(S O)))) = (S(S O)).
 539 normalize.reflexivity.
 540 qed.
 541
 542 theorem example3 : smallest_factor (S(S(S(S(S(S(S O))))))) = (S(S(S(S(S(S(S O))))))).
 543 simplify.reflexivity.
 544 qed. *)
 545
 546 theorem lt_SO_smallest_factor:
 547 \forall n:nat. (S O) < n \to (S O) < (smallest_factor n).
 548 intro.
 549 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O (S O) H).
 550 intro.apply (nat_case m).intro. apply False_ind.apply (not_le_Sn_n (S O) H).
 551 intros.
 552 change with
 553 (S O < min_aux m1 (S (S O)) (\lambda m.(eqb ((S(S m1)) \mod m) O))).
 554 apply (lt_to_le_to_lt ? (S (S O))).
 555 apply (le_n (S(S O))).
 556 cut ((S(S O)) = (S(S m1)) - m1).
 557 rewrite > Hcut.
 558 apply le_min_aux.
 559 apply sym_eq.apply plus_to_minus.
 560 rewrite < sym_plus.simplify.reflexivity.
 561 qed.
 562
 563 theorem lt_O_smallest_factor: \forall n:nat. O < n \to O < (smallest_factor n).
 564 intro.
 565 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_n O H).
 566 intro.apply (nat_case m).intro.
 567 simplify.unfold lt.apply le_n.
 568 intros.apply (trans_lt ? (S O)).
 569 unfold lt.apply le_n.
 570 apply lt_SO_smallest_factor.unfold lt. apply le_S_S.
 571 apply le_S_S.apply le_O_n.
 572 qed.
 573
 574 theorem divides_smallest_factor_n :
 575 \forall n:nat. O < n \to smallest_factor n \divides n.
 576 intro.
 577 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O O H).
 578 intro.apply (nat_case m).intro. simplify.
 579 apply (witness ? ? (S O)). simplify.reflexivity.
 580 intros.
 581 apply divides_b_true_to_divides.
 582 change with
 583 (eqb ((S(S m1)) \mod (min_aux m1 (S (S O))
 584   (\lambda m.(eqb ((S(S m1)) \mod m) O)))) O = true).
 585 apply f_min_aux_true.
 586 apply (ex_intro nat ? (S(S m1))).
 587 split.split.
 588 apply (le_S_S_to_le (S (S O)) (S (S m1)) ?).
 589 apply (minus_le_O_to_le (S (S (S O))) (S (S (S m1))) ?).
 590 apply (le_n O).
 591 rewrite < sym_plus. simplify. apply le_n.
 592 apply (eq_to_eqb_true (mod (S (S m1)) (S (S m1))) O ?).
 593 apply (mod_n_n (S (S m1)) ?).
 594 apply (H).
 595 qed.
 596
 597 theorem le_smallest_factor_n :
 598 \forall n:nat. smallest_factor n \le n.
 599 intro.apply (nat_case n).simplify.apply le_n.
 600 intro.apply (nat_case m).simplify.apply le_n.
 601 intro.apply divides_to_le.
 602 unfold lt.apply le_S_S.apply le_O_n.
 603 apply divides_smallest_factor_n.
 604 unfold lt.apply le_S_S.apply le_O_n.
 605 qed.
 606
 607 theorem lt_smallest_factor_to_not_divides: \forall n,i:nat.
 608 (S O) < n \to (S O) < i \to i < (smallest_factor n) \to i \ndivides n.
 609 intros 2.
 610 apply (nat_case n).intro.apply False_ind.apply (not_le_Sn_O (S O) H).
 611 intro.apply (nat_case m).intro. apply False_ind.apply (not_le_Sn_n (S O) H).
 612 intros.
 613 apply divides_b_false_to_not_divides.
 614 apply (lt_min_aux_to_false
 615 (\lambda i:nat.eqb ((S(S m1)) \mod i) O) (S (S O)) m1 i).
 616 assumption.
 617 assumption.
 618 qed.
 619
 620 theorem prime_smallest_factor_n :
 621 \forall n:nat. (S O) < n \to prime (smallest_factor n).
 622 intro.change with ((S(S O)) \le n \to (S O) < (smallest_factor n) \land
 623 (\forall m:nat. m \divides smallest_factor n \to (S O) < m \to  m = (smallest_factor n))).
 624 intro.split.
 625 apply lt_SO_smallest_factor.assumption.
 626 intros.
 627 cut (le m (smallest_factor n)).
 628 elim (le_to_or_lt_eq m (smallest_factor n) Hcut).
 629 absurd (m \divides n).
 630 apply (transitive_divides m (smallest_factor n)).
 631 assumption.
 632 apply divides_smallest_factor_n.
 633 apply (trans_lt ? (S O)). unfold lt. apply le_n. exact H.
 634 apply lt_smallest_factor_to_not_divides.
 635 exact H.assumption.assumption.assumption.
 636 apply divides_to_le.
 637 apply (trans_lt O (S O)).
 638 apply (le_n (S O)).
 639 apply lt_SO_smallest_factor.
 640 exact H.
 641 assumption.
 642 qed.
 643
 644 theorem prime_to_smallest_factor: \forall n. prime n \to
 645 smallest_factor n = n.
 646 intro.apply (nat_case n).intro.apply False_ind.apply (not_prime_O H).
 647 intro.apply (nat_case m).intro.apply False_ind.apply (not_prime_SO H).
 648 intro.
 649 change with
 650 ((S O) < (S(S m1)) \land
 651 (\forall m:nat. m \divides S(S m1) \to (S O) < m \to  m = (S(S m1))) \to
 652 smallest_factor (S(S m1)) = (S(S m1))).
 653 intro.elim H.apply H2.
 654 apply divides_smallest_factor_n.
 655 apply (trans_lt ? (S O)).unfold lt. apply le_n.assumption.
 656 apply lt_SO_smallest_factor.
 657 assumption.
 658 qed.
 659
 660 (* a number n > O is prime iff its smallest factor is n *)
 661 definition primeb \def \lambda n:nat.
 662 match n with
 663 [ O \Rightarrow false
 664 | (S p) \Rightarrow
 665   match p with
 666   [ O \Rightarrow false
 667   | (S q) \Rightarrow eqb (smallest_factor (S(S q))) (S(S q))]].
 668
 669 (* it works!
 670 theorem example4 : primeb (S(S(S O))) = true.
 671 normalize.reflexivity.
 672 qed.
 673
 674 theorem example5 : primeb (S(S(S(S(S(S O)))))) = false.
 675 normalize.reflexivity.
 676 qed.
 677
 678 theorem example6 : primeb (S(S(S(S((S(S(S(S(S(S(S O)))))))))))) = true.
 679 normalize.reflexivity.
 680 qed.
 681
 682 theorem example7 : primeb (S(S(S(S(S(S((S(S(S(S((S(S(S(S(S(S(S O))))))))))))))))))) = true.
 683 normalize.reflexivity.
 684 qed. *)
 685
 686 theorem primeb_to_Prop: \forall n.
 687 match primeb n with
 688 [ true \Rightarrow prime n
 689 | false \Rightarrow \lnot (prime n)].
 690 intro.
 691 apply (nat_case n).simplify.unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_O (S O) H1).
 692 intro.apply (nat_case m).simplify.unfold Not.unfold prime.intro.elim H.apply (not_le_Sn_n (S O) H1).
 693 intro.
 694 change with
 695 match eqb (smallest_factor (S(S m1))) (S(S m1)) with
 696 [ true \Rightarrow prime (S(S m1))
 697 | false \Rightarrow \lnot (prime (S(S m1)))].
 698 apply (eqb_elim (smallest_factor (S(S m1))) (S(S m1))).
 699 intro.simplify.
 700 rewrite < H.
 701 apply prime_smallest_factor_n.
 702 unfold lt.apply le_S_S.apply le_S_S.apply le_O_n.
 703 intro.simplify.
 704 change with (prime (S(S m1)) \to False).
 705 intro.apply H.
 706 apply prime_to_smallest_factor.
 707 assumption.
 708 qed.
 709
 710 theorem primeb_true_to_prime : \forall n:nat.
 711 primeb n = true \to prime n.
 712 intros.change with
 713 match true with
 714 [ true \Rightarrow prime n
 715 | false \Rightarrow \lnot (prime n)].
 716 rewrite < H.
 717 apply primeb_to_Prop.
 718 qed.
 719
 720 theorem primeb_false_to_not_prime : \forall n:nat.
 721 primeb n = false \to \lnot (prime n).
 722 intros.change with
 723 match false with
 724 [ true \Rightarrow prime n
 725 | false \Rightarrow \lnot (prime n)].
 726 rewrite < H.
 727 apply primeb_to_Prop.
 728 qed.
 729
 730 theorem decidable_prime : \forall n:nat.decidable (prime n).
 731 intro.unfold decidable.
 732 cut
 733 (match primeb n with
 734 [ true \Rightarrow prime n
 735 | false \Rightarrow \lnot (prime n)] \to (prime n) \lor \lnot (prime n)).
 736 apply Hcut.apply primeb_to_Prop.
 737 elim (primeb n).left.apply H.right.apply H.
 738 qed.
 739
 740 theorem prime_to_primeb_true: \forall n:nat.
 741 prime n \to primeb n = true.
 742 intros.
 743 cut (match (primeb n) with
 744 [ true \Rightarrow prime n
 745 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = true)).
 746 apply Hcut.apply primeb_to_Prop.
 747 elim (primeb n).reflexivity.
 748 absurd (prime n).assumption.assumption.
 749 qed.
 750
 751 theorem not_prime_to_primeb_false: \forall n:nat.
 752 \lnot(prime n) \to primeb n = false.
 753 intros.
 754 cut (match (primeb n) with
 755 [ true \Rightarrow prime n
 756 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = false)).
 757 apply Hcut.apply primeb_to_Prop.
 758 elim (primeb n).
 759 absurd (prime n).assumption.assumption.
 760 reflexivity.
 761 qed.
 762