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 theorem reflexive_divides : reflexive nat divides.
  26 simplify.
  27 intros.
  28 exact witness x x (S O) (times_n_SO x).
  29 qed.
  30
  31 theorem divides_to_div_mod_spec :
  32 \forall n,m. O < n \to divides n m \to div_mod_spec m n (div m n) O.
  33 intros.elim H1.rewrite > H2.
  34 constructor 1.assumption.
  35 apply lt_O_n_elim n H.intros.
  36 rewrite < plus_n_O.
  37 rewrite > div_times.apply sym_times.
  38 qed.
  39
  40 theorem div_mod_spec_to_div :
  41 \forall n,m,p. div_mod_spec m n p O \to divides n m.
  42 intros.elim H.
  43 apply witness n m p.
  44 rewrite < sym_times.
  45 rewrite > plus_n_O (p*n).assumption.
  46 qed.
  47
  48 theorem divides_to_mod_O:
  49 \forall n,m. O < n \to divides n m \to (mod m n) = O.
  50 intros.apply div_mod_spec_to_eq2 m n (div m n) (mod m n) (div m n) O.
  51 apply div_mod_spec_div_mod.assumption.
  52 apply divides_to_div_mod_spec.assumption.assumption.
  53 qed.
  54
  55 theorem mod_O_to_divides:
  56 \forall n,m. O< n \to (mod m n) = O \to  divides n m.
  57 intros.
  58 apply witness n m (div m n).
  59 rewrite > plus_n_O (n*div m n).
  60 rewrite < H1.
  61 rewrite < sym_times.
  62 (* perche' hint non lo trova ?*)
  63 apply div_mod.
  64 assumption.
  65 qed.
  66
  67 theorem divides_n_O: \forall n:nat. divides n O.
  68 intro. apply witness n O O.apply times_n_O.
  69 qed.
  70
  71 theorem divides_SO_n: \forall n:nat. divides (S O) n.
  72 intro. apply witness (S O) n n. simplify.apply plus_n_O.
  73 qed.
  74
  75 theorem divides_plus: \forall n,p,q:nat.
  76 divides n p \to divides n q \to divides n (p+q).
  77 intros.
  78 elim H.elim H1. apply witness n (p+q) (n2+n1).
  79 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_plus.
  80 qed.
  81
  82 theorem divides_minus: \forall n,p,q:nat.
  83 divides n p \to divides n q \to divides n (p-q).
  84 intros.
  85 elim H.elim H1. apply witness n (p-q) (n2-n1).
  86 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_minus.
  87 qed.
  88
  89 theorem divides_times: \forall n,m,p,q:nat.
  90 divides n p \to divides m q \to divides (n*m) (p*q).
  91 intros.
  92 elim H.elim H1. apply witness (n*m) (p*q) (n2*n1).
  93 rewrite > H2.rewrite > H3.
  94 apply trans_eq nat ? (n*(m*(n2*n1))).
  95 apply trans_eq nat ? (n*(n2*(m*n1))).
  96 apply assoc_times.
  97 apply eq_f.
  98 apply trans_eq nat ? ((n2*m)*n1).
  99 apply sym_eq. apply assoc_times.
 100 rewrite > sym_times n2 m.apply assoc_times.
 101 apply sym_eq. apply assoc_times.
 102 qed.
 103
 104 theorem transitive_divides: \forall n,m,p.
 105 divides n m \to divides m p \to divides n p.
 106 intros.
 107 elim H.elim H1. apply witness n p (n2*n1).
 108 rewrite > H3.rewrite > H2.
 109 apply assoc_times.
 110 qed.
 111
 112 (* divides le *)
 113 theorem divides_to_le : \forall n,m. O < m \to divides n m \to n \le m.
 114 intros. elim H1.rewrite > H2.cut O < n2.
 115 apply lt_O_n_elim n2 Hcut.intro.rewrite < sym_times.
 116 simplify.rewrite < sym_plus.
 117 apply le_plus_n.
 118 elim le_to_or_lt_eq O n2.
 119 assumption.apply le_O_n.
 120 absurd O<m.assumption.
 121 rewrite > H2.rewrite < H3.rewrite < times_n_O.
 122 apply not_le_Sn_n O.
 123 qed.
 124
 125 theorem divides_to_lt_O : \forall n,m. O < m \to divides n m \to O < n.
 126 intros.elim H1.
 127 elim le_to_or_lt_eq O n (le_O_n n).
 128 assumption.
 129 rewrite < H3.absurd O < m.assumption.
 130 rewrite > H2.rewrite < H3.
 131 simplify.exact not_le_Sn_n O.
 132 qed.
 133
 134 (* boolean divides *)
 135 definition divides_b : nat \to nat \to bool \def
 136 \lambda n,m :nat. (eqb (mod m n) O).
 137
 138 theorem divides_b_to_Prop :
 139 \forall n,m:nat. O < n \to O < m \to
 140 match divides_b n m with
 141 [ true \Rightarrow divides n m
 142 | false \Rightarrow \lnot (divides n m)].
 143 intros.
 144 change with
 145 match eqb (mod m n) O with
 146 [ true \Rightarrow divides n m
 147 | false \Rightarrow \lnot (divides n m)].
 148 apply eqb_elim.
 149 intro.simplify.apply mod_O_to_divides.assumption.assumption.
 150 intro.simplify.intro.apply H2.apply divides_to_mod_O.assumption.assumption.
 151 qed.
 152
 153 theorem divides_b_true_to_divides :
 154 \forall n,m:nat. O < n \to O < m \to
 155 (divides_b n m = true ) \to divides n m.
 156 intros.
 157 change with
 158 match true with
 159 [ true \Rightarrow divides n m
 160 | false \Rightarrow \lnot (divides n m)].
 161 rewrite < H2.apply divides_b_to_Prop.
 162 assumption.assumption.
 163 qed.
 164
 165 theorem divides_b_false_to_not_divides :
 166 \forall n,m:nat. O < n \to O < m \to
 167 (divides_b n m = false ) \to \lnot (divides n m).
 168 intros.
 169 change with
 170 match false with
 171 [ true \Rightarrow divides n m
 172 | false \Rightarrow \lnot (divides n m)].
 173 rewrite < H2.apply divides_b_to_Prop.
 174 assumption.assumption.
 175 qed.
 176
 177 (* divides and pi *)
 178 theorem divides_f_pi_f : \forall f:nat \to nat.\forall n,i:nat.
 179 i < n \to divides (f i) (pi n f).
 180 intros 3.elim n.apply False_ind.apply not_le_Sn_O i H.
 181 simplify.
 182 apply le_n_Sm_elim (S i) n1 H1.
 183 intro.
 184 apply transitive_divides ? (pi n1 f).
 185 apply H.simplify.apply le_S_S_to_le. assumption.
 186 apply witness ? ? (f n1).apply sym_times.
 187 intro.cut i = n1.
 188 rewrite > Hcut.
 189 apply witness ? ? (pi n1 f).reflexivity.
 190 apply inj_S.assumption.
 191 qed.
 192
 193 theorem mod_S_pi: \forall f:nat \to nat.\forall n,i:nat.
 194 i < n \to (S O) < (f i) \to mod (S (pi n f)) (f i) = (S O).
 195 intros.cut mod (pi n f) (f i) = O.
 196 rewrite < Hcut.
 197 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
 198 rewrite > Hcut.assumption.
 199 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
 200 apply divides_f_pi_f.assumption.
 201 qed.
 202
 203 (* divides and fact *)
 204 theorem divides_fact : \forall n,i:nat.
 205 O < i \to i \le n \to divides i (fact n).
 206 intros 3.elim n.absurd O<i.assumption.apply le_n_O_elim i H1.
 207 apply not_le_Sn_O O.
 208 change with divides i ((S n1)*(fact n1)).
 209 apply le_n_Sm_elim i n1 H2.
 210 intro.
 211 apply transitive_divides ? (fact n1).
 212 apply H1.apply le_S_S_to_le. assumption.
 213 apply witness ? ? (S n1).apply sym_times.
 214 intro.
 215 rewrite > H3.
 216 apply witness ? ? (fact n1).reflexivity.
 217 qed.
 218
 219 theorem mod_S_fact: \forall n,i:nat.
 220 (S O) < i \to i \le n \to mod (S (fact n)) i = (S O).
 221 intros.cut mod (fact n) i = O.
 222 rewrite < Hcut.
 223 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
 224 rewrite > Hcut.assumption.
 225 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
 226 apply divides_fact.apply trans_lt O (S O).apply le_n (S O).assumption.
 227 assumption.
 228 qed.
 229
 230 theorem not_divides_S_fact: \forall n,i:nat.
 231 (S O) < i \to i \le n \to \not (divides i (S (fact n))).
 232 intros.
 233 apply divides_b_false_to_not_divides.
 234 apply trans_lt O (S O).apply le_n (S O).assumption.
 235 simplify.apply le_S_S.apply le_O_n.
 236 change with (eqb (mod (S (fact n)) i) O) = false.
 237 rewrite > mod_S_fact.simplify.reflexivity.
 238 assumption.assumption.
 239 qed.
 240
 241 (* prime *)
 242 definition prime : nat \to  Prop \def
 243 \lambda n:nat. (S O) < n \land
 244 (\forall m:nat. divides m n \to (S O) < m \to  m = n).
 245
 246 theorem not_prime_O: \lnot (prime O).
 247 simplify.intro.elim H.apply not_le_Sn_O (S O) H1.
 248 qed.
 249
 250 theorem not_prime_SO: \lnot (prime (S O)).
 251 simplify.intro.elim H.apply not_le_Sn_n (S O) H1.
 252 qed.
 253
 254 (* smallest factor *)
 255 definition smallest_factor : nat \to nat \def
 256 \lambda n:nat.
 257 match n with
 258 [ O \Rightarrow O
 259 | (S p) \Rightarrow
 260   match p with
 261   [ O \Rightarrow (S O)
 262   | (S q) \Rightarrow min_aux q (S(S q)) (\lambda m.(eqb (mod (S(S q)) m) O))]].
 263
 264 (* it works !
 265 theorem example1 : smallest_prime_factor (S(S(S O))) = (S(S(S O))).
 266 normalize.reflexivity.
 267 qed.
 268
 269 theorem example2: smallest_prime_factor (S(S(S(S O)))) = (S(S O)).
 270 normalize.reflexivity.
 271 qed.
 272
 273 theorem example3 : smallest_prime_factor (S(S(S(S(S(S(S O))))))) = (S(S(S(S(S(S(S O))))))).
 274 simplify.reflexivity.
 275 qed. *)
 276
 277 (* not sure this is what we need *)
 278 theorem lt_S_O_smallest_factor:
 279 \forall n:nat. (S O) < n \to (S O) < (smallest_factor n).
 280 intro.
 281 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
 282 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
 283 intros.
 284 change with
 285 S O < min_aux m1 (S(S m1)) (\lambda m.(eqb (mod (S(S m1)) m) O)).
 286 apply lt_to_le_to_lt ? (S (S O)).
 287 apply le_n (S(S O)).
 288 cut (S(S O)) = (S(S m1)) - m1.
 289 rewrite > Hcut.
 290 apply le_min_aux.
 291 apply sym_eq.apply plus_to_minus.apply le_S.apply le_n_Sn.
 292 rewrite < sym_plus.simplify.reflexivity.
 293 qed.
 294
 295 theorem divides_smallest_factor_n :
 296 \forall n:nat. (S O) < n \to divides (smallest_factor n) n.
 297 intro.
 298 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
 299 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
 300 intros.
 301 apply divides_b_true_to_divides.
 302 apply trans_lt ? (S O).apply le_n (S O).apply lt_S_O_smallest_factor ? H.
 303 apply trans_lt ? (S O).apply le_n (S O).assumption.
 304 change with
 305 eqb (mod (S(S m1)) (min_aux m1 (S(S m1))
 306   (\lambda m.(eqb (mod (S(S m1)) m) O)))) O = true.
 307 apply f_min_aux_true.
 308 apply ex_intro nat ? (S(S m1)).
 309 split.split.
 310 apply le_minus_m.apply le_n.
 311 rewrite > mod_n_n.reflexivity.
 312 apply trans_lt ? (S O).apply le_n (S O).assumption.
 313 qed.
 314
 315 theorem le_smallest_factor_n :
 316 \forall n:nat. smallest_factor n \le n.
 317 intro.apply nat_case n.simplify.reflexivity.
 318 intro.apply nat_case m.simplify.reflexivity.
 319 intro.apply divides_to_le.
 320 simplify.apply le_S_S.apply le_O_n.
 321 apply divides_smallest_factor_n.
 322 simplify.apply le_S_S.apply le_S_S. apply le_O_n.
 323 qed.
 324
 325 theorem lt_smallest_factor_to_not_divides: \forall n,i:nat.
 326 (S O) < n \to (S O) < i \to i < (smallest_factor n) \to \lnot (divides i n).
 327 intros 2.
 328 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
 329 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
 330 intros.
 331 apply divides_b_false_to_not_divides.
 332 apply trans_lt O (S O).apply le_n (S O).assumption.
 333 apply trans_lt O (S O).apply le_n (S O).assumption.
 334 change with (eqb (mod (S(S m1)) i) O) = false.
 335 apply lt_min_aux_to_false
 336 (\lambda i:nat.eqb (mod (S(S m1)) i) O) (S(S m1)) m1 i.
 337 cut (S(S O)) = (S(S m1)-m1).
 338 rewrite < Hcut.exact H1.
 339 apply sym_eq. apply plus_to_minus.
 340 apply le_S.apply le_n_Sn.
 341 rewrite < sym_plus.simplify.reflexivity.
 342 exact H2.
 343 qed.
 344
 345 theorem prime_smallest_factor_n :
 346 \forall n:nat. (S O) < n \to prime (smallest_factor n).
 347 intro. change with (S(S O)) \le n \to (S O) < (smallest_factor n) \land
 348 (\forall m:nat. divides m (smallest_factor n) \to (S O) < m \to  m = (smallest_factor n)).
 349 intro.split.
 350 apply lt_S_O_smallest_factor.assumption.
 351 intros.
 352 cut le m (smallest_factor n).
 353 elim le_to_or_lt_eq m (smallest_factor n) Hcut.
 354 absurd divides m n.
 355 apply transitive_divides m (smallest_factor n).
 356 assumption.
 357 apply divides_smallest_factor_n.
 358 exact H.
 359 apply lt_smallest_factor_to_not_divides.
 360 exact H.assumption.assumption.assumption.
 361 apply divides_to_le.
 362 apply trans_lt O (S O).
 363 apply le_n (S O).
 364 apply lt_S_O_smallest_factor.
 365 exact H.
 366 assumption.
 367 qed.
 368
 369 theorem prime_to_smallest_factor: \forall n. prime n \to
 370 smallest_factor n = n.
 371 intro.apply nat_case n.intro.apply False_ind.apply not_prime_O H.
 372 intro.apply nat_case m.intro.apply False_ind.apply not_prime_SO H.
 373 intro.
 374 change with
 375 (S O) < (S(S m1)) \land
 376 (\forall m:nat. divides m (S(S m1)) \to (S O) < m \to  m = (S(S m1))) \to
 377 smallest_factor (S(S m1)) = (S(S m1)).
 378 intro.elim H.apply H2.
 379 apply divides_smallest_factor_n.
 380 assumption.
 381 apply lt_S_O_smallest_factor.
 382 assumption.
 383 qed.
 384
 385 (* a number n > O is prime iff its smallest factor is n *)
 386 definition primeb \def \lambda n:nat.
 387 match n with
 388 [ O \Rightarrow false
 389 | (S p) \Rightarrow
 390   match p with
 391   [ O \Rightarrow false
 392   | (S q) \Rightarrow eqb (smallest_factor (S(S q))) (S(S q))]].
 393
 394 (* it works!
 395 theorem example4 : primeb (S(S(S O))) = true.
 396 normalize.reflexivity.
 397 qed.
 398
 399 theorem example5 : primeb (S(S(S(S(S(S O)))))) = false.
 400 normalize.reflexivity.
 401 qed.
 402
 403 theorem example6 : primeb (S(S(S(S((S(S(S(S(S(S(S O)))))))))))) = true.
 404 normalize.reflexivity.
 405 qed.
 406
 407 theorem example7 : primeb (S(S(S(S(S(S((S(S(S(S((S(S(S(S(S(S(S O))))))))))))))))))) = true.
 408 normalize.reflexivity.
 409 qed. *)
 410
 411 theorem primeb_to_Prop: \forall n.
 412 match primeb n with
 413 [ true \Rightarrow prime n
 414 | false \Rightarrow \not (prime n)].
 415 intro.
 416 apply nat_case n.simplify.intro.elim H.apply not_le_Sn_O (S O) H1.
 417 intro.apply nat_case m.simplify.intro.elim H.apply not_le_Sn_n (S O) H1.
 418 intro.
 419 change with
 420 match eqb (smallest_factor (S(S m1))) (S(S m1)) with
 421 [ true \Rightarrow prime (S(S m1))
 422 | false \Rightarrow \not (prime (S(S m1)))].
 423 apply eqb_elim (smallest_factor (S(S m1))) (S(S m1)).
 424 intro.change with prime (S(S m1)).
 425 rewrite < H.
 426 apply prime_smallest_factor_n.
 427 simplify.apply le_S_S.apply le_S_S.apply le_O_n.
 428 intro.change with \not (prime (S(S m1))).
 429 change with prime (S(S m1)) \to False.
 430 intro.apply H.
 431 apply prime_to_smallest_factor.
 432 assumption.
 433 qed.
 434
 435 theorem primeb_true_to_prime : \forall n:nat.
 436 primeb n = true \to prime n.
 437 intros.change with
 438 match true with
 439 [ true \Rightarrow prime n
 440 | false \Rightarrow \not (prime n)].
 441 rewrite < H.
 442 apply primeb_to_Prop.
 443 qed.
 444
 445 theorem primeb_false_to_not_prime : \forall n:nat.
 446 primeb n = false \to \not (prime n).
 447 intros.change with
 448 match false with
 449 [ true \Rightarrow prime n
 450 | false \Rightarrow \not (prime n)].
 451 rewrite < H.
 452 apply primeb_to_Prop.
 453 qed.
 454
 455 theorem decidable_prime : \forall n:nat.decidable (prime n).
 456 intro.change with (prime n) \lor \not (prime n).
 457 cut
 458 match primeb n with
 459 [ true \Rightarrow prime n
 460 | false \Rightarrow \not (prime n)] \to (prime n) \lor \not (prime n).
 461 apply Hcut.apply primeb_to_Prop.
 462 elim (primeb n).left.apply H.right.apply H.
 463 qed.
 464
 465 theorem prime_to_primeb_true: \forall n:nat.
 466 prime n \to primeb n = true.
 467 intros.
 468 cut match (primeb n) with
 469 [ true \Rightarrow prime n
 470 | false \Rightarrow \not (prime n)] \to ((primeb n) = true).
 471 apply Hcut.apply primeb_to_Prop.
 472 elim primeb n.reflexivity.
 473 absurd (prime n).assumption.assumption.
 474 qed.
 475
 476 theorem not_prime_to_primeb_false: \forall n:nat.
 477 \not(prime n) \to primeb n = false.
 478 intros.
 479 cut match (primeb n) with
 480 [ true \Rightarrow prime n
 481 | false \Rightarrow \not (prime n)] \to ((primeb n) = false).
 482 apply Hcut.apply primeb_to_Prop.
 483 elim primeb n.
 484 absurd (prime n).assumption.assumption.
 485 reflexivity.
 486 qed.
 487
 488 (* upper bound by Bertrand's conjecture. *)
 489 (* Too difficult to prove.
 490 let rec nth_prime n \def
 491 match n with
 492   [ O \Rightarrow (S(S O))
 493   | (S p) \Rightarrow
 494     let previous_prime \def S (nth_prime p) in
 495     min_aux previous_prime ((S(S O))*previous_prime) primeb].
 496
 497 theorem example8 : nth_prime (S(S O)) = (S(S(S(S(S O))))).
 498 normalize.reflexivity.
 499 qed.
 500
 501 theorem example9 : nth_prime (S(S(S O))) = (S(S(S(S(S(S(S O))))))).
 502 normalize.reflexivity.
 503 qed.
 504
 505 theorem example10 : nth_prime (S(S(S(S O)))) = (S(S(S(S(S(S(S(S(S(S(S O))))))))))).
 506 normalize.reflexivity.
 507 qed. *)
 508
 509 theorem smallest_factor_fact: \forall n:nat.
 510 n < smallest_factor (S (fact n)).
 511 intros.
 512 apply not_le_to_lt.
 513 change with smallest_factor (S (fact n)) \le n \to False.intro.
 514 apply not_divides_S_fact n (smallest_factor(S (fact n))) ? ?.
 515 apply divides_smallest_factor_n.
 516 simplify.apply le_S_S.apply le_SO_fact.
 517 apply lt_S_O_smallest_factor.
 518 simplify.apply le_S_S.apply le_SO_fact.
 519 assumption.
 520 qed.
 521
 522 (* mi sembra che il problem sia ex *)
 523 theorem ex_prime: \forall n. (S O) \le n \to ex nat (\lambda m.
 524 n < m \land m \le (S (fact n)) \land (prime m)).
 525 intros.
 526 elim H.
 527 apply ex_intro nat ? (S(S O)).
 528 split.split.apply le_n (S(S O)).
 529 apply le_n (S(S O)).apply primeb_to_Prop (S(S O)).
 530 apply ex_intro nat ? (smallest_factor (S (fact (S n1)))).
 531 split.split.
 532 apply smallest_factor_fact.
 533 apply le_smallest_factor_n.
 534 (* ancora hint non lo trova *)
 535 apply prime_smallest_factor_n.
 536 change with (S(S O)) \le S (fact (S n1)).
 537 apply le_S.apply le_SSO_fact.
 538 simplify.apply le_S_S.assumption.
 539 qed.
 540
 541 let rec nth_prime n \def
 542 match n with
 543   [ O \Rightarrow (S(S O))
 544   | (S p) \Rightarrow
 545     let previous_prime \def (nth_prime p) in
 546     let upper_bound \def S (fact previous_prime) in
 547     min_aux (upper_bound - (S previous_prime)) upper_bound primeb].
 548
 549 (* it works, but nth_prime 4 takes already a few minutes -
 550 it must compute factorial of 7 ...
 551
 552 theorem example11 : nth_prime (S(S O)) = (S(S(S(S(S O))))).
 553 normalize.reflexivity.
 554 qed.
 555
 556 theorem example12: nth_prime (S(S(S O))) = (S(S(S(S(S(S(S O))))))).
 557 normalize.reflexivity.
 558 qed.
 559
 560 theorem example13 : nth_prime (S(S(S(S O)))) = (S(S(S(S(S(S(S(S(S(S(S O))))))))))).
 561 normalize.reflexivity.
 562 *)
 563
 564 theorem prime_nth_prime : \forall n:nat.prime (nth_prime n).
 565 intro.
 566 apply nat_case n.
 567 change with prime (S(S O)).
 568 apply primeb_to_Prop (S(S O)).
 569 intro.
 570 (* ammirare la resa del letin !! *)
 571 change with
 572 let previous_prime \def (nth_prime m) in
 573 let upper_bound \def S (fact previous_prime) in
 574 prime (min_aux (upper_bound - (S previous_prime)) upper_bound primeb).
 575 apply primeb_true_to_prime.
 576 apply f_min_aux_true.
 577 apply ex_intro nat ? (smallest_factor (S (fact (nth_prime m)))).
 578 split.split.
 579 cut S (fact (nth_prime m))-(S (fact (nth_prime m)) - (S (nth_prime m))) = (S (nth_prime m)).
 580 rewrite > Hcut.exact smallest_factor_fact (nth_prime m).
 581 (* maybe we could factorize this proof *)
 582 apply plus_to_minus.
 583 apply le_minus_m.
 584 apply plus_minus_m_m.
 585 apply le_S_S.
 586 apply le_n_fact_n.
 587 apply le_smallest_factor_n.
 588 apply prime_to_primeb_true.
 589 apply prime_smallest_factor_n.
 590 change with (S(S O)) \le S (fact (nth_prime m)).
 591 apply le_S_S.apply le_SO_fact.
 592 qed.