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 (div 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 (mod m n) = O.
  54 intros.apply div_mod_spec_to_eq2 m n (div m n) (mod m n) (div 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 (mod m n) = O \to  n \divides m.
  61 intros.
  62 apply witness n m (div m n).
  63 rewrite > plus_n_O (n*div 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_SO_n: \forall n:nat. (S O) \divides n.
  76 intro. apply witness (S O) n n. simplify.apply plus_n_O.
  77 qed.
  78
  79 theorem divides_plus: \forall n,p,q:nat.
  80 n \divides p \to n \divides q \to n \divides p+q.
  81 intros.
  82 elim H.elim H1. apply witness n (p+q) (n2+n1).
  83 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_plus.
  84 qed.
  85
  86 theorem divides_minus: \forall n,p,q:nat.
  87 divides n p \to divides n q \to divides n (p-q).
  88 intros.
  89 elim H.elim H1. apply witness n (p-q) (n2-n1).
  90 rewrite > H2.rewrite > H3.apply sym_eq.apply distr_times_minus.
  91 qed.
  92
  93 theorem divides_times: \forall n,m,p,q:nat.
  94 n \divides p \to m \divides q \to n*m \divides p*q.
  95 intros.
  96 elim H.elim H1. apply witness (n*m) (p*q) (n2*n1).
  97 rewrite > H2.rewrite > H3.
  98 apply trans_eq nat ? (n*(m*(n2*n1))).
  99 apply trans_eq nat ? (n*(n2*(m*n1))).
 100 apply assoc_times.
 101 apply eq_f.
 102 apply trans_eq nat ? ((n2*m)*n1).
 103 apply sym_eq. apply assoc_times.
 104 rewrite > sym_times n2 m.apply assoc_times.
 105 apply sym_eq. apply assoc_times.
 106 qed.
 107
 108 theorem transitive_divides: transitive ? divides.
 109 unfold.
 110 intros.
 111 elim H.elim H1. apply witness x z (n2*n).
 112 rewrite > H3.rewrite > H2.
 113 apply assoc_times.
 114 qed.
 115
 116 variant trans_divides: \forall n,m,p.
 117  n \divides m \to m \divides p \to n \divides p \def transitive_divides.
 118
 119 (* divides le *)
 120 theorem divides_to_le : \forall n,m. O < m \to n \divides m \to n \le m.
 121 intros. elim H1.rewrite > H2.cut O < n2.
 122 apply lt_O_n_elim n2 Hcut.intro.rewrite < sym_times.
 123 simplify.rewrite < sym_plus.
 124 apply le_plus_n.
 125 elim le_to_or_lt_eq O n2.
 126 assumption.
 127 absurd O<m.assumption.
 128 rewrite > H2.rewrite < H3.rewrite < times_n_O.
 129 apply not_le_Sn_n O.
 130 apply le_O_n.
 131 qed.
 132
 133 theorem divides_to_lt_O : \forall n,m. O < m \to n \divides m \to O < n.
 134 intros.elim H1.
 135 elim le_to_or_lt_eq O n (le_O_n n).
 136 assumption.
 137 rewrite < H3.absurd O < m.assumption.
 138 rewrite > H2.rewrite < H3.
 139 simplify.exact not_le_Sn_n O.
 140 qed.
 141
 142 (* boolean divides *)
 143 definition divides_b : nat \to nat \to bool \def
 144 \lambda n,m :nat. (eqb (mod m n) O).
 145
 146 theorem divides_b_to_Prop :
 147 \forall n,m:nat. O < n \to
 148 match divides_b n m with
 149 [ true \Rightarrow n \divides m
 150 | false \Rightarrow n \ndivides m].
 151 intros.
 152 change with
 153 match eqb (mod m n) O with
 154 [ true \Rightarrow n \divides m
 155 | false \Rightarrow n \ndivides m].
 156 apply eqb_elim.
 157 intro.simplify.apply mod_O_to_divides.assumption.assumption.
 158 intro.simplify.intro.apply H1.apply divides_to_mod_O.assumption.assumption.
 159 qed.
 160
 161 theorem divides_b_true_to_divides :
 162 \forall n,m:nat. O < n \to
 163 (divides_b n m = true ) \to n \divides m.
 164 intros.
 165 change with
 166 match true with
 167 [ true \Rightarrow n \divides m
 168 | false \Rightarrow n \ndivides m].
 169 rewrite < H1.apply divides_b_to_Prop.
 170 assumption.
 171 qed.
 172
 173 theorem divides_b_false_to_not_divides :
 174 \forall n,m:nat. O < n \to
 175 (divides_b n m = false ) \to n \ndivides m.
 176 intros.
 177 change with
 178 match false with
 179 [ true \Rightarrow n \divides m
 180 | false \Rightarrow n \ndivides m].
 181 rewrite < H1.apply divides_b_to_Prop.
 182 assumption.
 183 qed.
 184
 185 theorem decidable_divides: \forall n,m:nat.O < n \to
 186 decidable (n \divides m).
 187 intros.change with (n \divides m) \lor n \ndivides m.
 188 cut
 189 match divides_b n m with
 190 [ true \Rightarrow n \divides m
 191 | false \Rightarrow n \ndivides m] \to n \divides m \lor n \ndivides m.
 192 apply Hcut.apply divides_b_to_Prop.assumption.
 193 elim (divides_b n m).left.apply H1.right.apply H1.
 194 qed.
 195
 196 theorem divides_to_divides_b_true : \forall n,m:nat. O < n \to
 197 n \divides m \to divides_b n m = true.
 198 intros.
 199 cut match (divides_b n m) with
 200 [ true \Rightarrow n \divides m
 201 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = true).
 202 apply Hcut.apply divides_b_to_Prop.assumption.
 203 elim divides_b n m.reflexivity.
 204 absurd (n \divides m).assumption.assumption.
 205 qed.
 206
 207 theorem not_divides_to_divides_b_false: \forall n,m:nat. O < n \to
 208 \lnot(n \divides m) \to (divides_b n m) = false.
 209 intros.
 210 cut match (divides_b n m) with
 211 [ true \Rightarrow n \divides m
 212 | false \Rightarrow n \ndivides m] \to ((divides_b n m) = false).
 213 apply Hcut.apply divides_b_to_Prop.assumption.
 214 elim divides_b n m.
 215 absurd (n \divides m).assumption.assumption.
 216 reflexivity.
 217 qed.
 218
 219 (* divides and pi *)
 220 theorem divides_f_pi_f : \forall f:nat \to nat.\forall n,i:nat.
 221 i < n \to f i \divides pi n f.
 222 intros 3.elim n.apply False_ind.apply not_le_Sn_O i H.
 223 simplify.
 224 apply le_n_Sm_elim (S i) n1 H1.
 225 intro.
 226 apply transitive_divides ? (pi n1 f).
 227 apply H.simplify.apply le_S_S_to_le. assumption.
 228 apply witness ? ? (f n1).apply sym_times.
 229 intro.cut i = n1.
 230 rewrite > Hcut.
 231 apply witness ? ? (pi n1 f).reflexivity.
 232 apply inj_S.assumption.
 233 qed.
 234
 235 theorem mod_S_pi: \forall f:nat \to nat.\forall n,i:nat.
 236 i < n \to (S O) < (f i) \to mod (S (pi n f)) (f i) = (S O).
 237 intros.cut mod (pi n f) (f i) = O.
 238 rewrite < Hcut.
 239 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
 240 rewrite > Hcut.assumption.
 241 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
 242 apply divides_f_pi_f.assumption.
 243 qed.
 244
 245 (* divides and fact *)
 246 theorem divides_fact : \forall n,i:nat.
 247 O < i \to i \le n \to i \divides n!.
 248 intros 3.elim n.absurd O<i.assumption.apply le_n_O_elim i H1.
 249 apply not_le_Sn_O O.
 250 change with i \divides (S n1)*n1!.
 251 apply le_n_Sm_elim i n1 H2.
 252 intro.
 253 apply transitive_divides ? n1!.
 254 apply H1.apply le_S_S_to_le. assumption.
 255 apply witness ? ? (S n1).apply sym_times.
 256 intro.
 257 rewrite > H3.
 258 apply witness ? ? n1!.reflexivity.
 259 qed.
 260
 261 theorem mod_S_fact: \forall n,i:nat.
 262 (S O) < i \to i \le n \to mod (S n!) i = (S O).
 263 intros.cut mod n! i = O.
 264 rewrite < Hcut.
 265 apply mod_S.apply trans_lt O (S O).apply le_n (S O).assumption.
 266 rewrite > Hcut.assumption.
 267 apply divides_to_mod_O.apply trans_lt O (S O).apply le_n (S O).assumption.
 268 apply divides_fact.apply trans_lt O (S O).apply le_n (S O).assumption.
 269 assumption.
 270 qed.
 271
 272 theorem not_divides_S_fact: \forall n,i:nat.
 273 (S O) < i \to i \le n \to i \ndivides S n!.
 274 intros.
 275 apply divides_b_false_to_not_divides.
 276 apply trans_lt O (S O).apply le_n (S O).assumption.
 277 change with (eqb (mod (S n!) i) O) = false.
 278 rewrite > mod_S_fact.simplify.reflexivity.
 279 assumption.assumption.
 280 qed.
 281
 282 (* prime *)
 283 definition prime : nat \to  Prop \def
 284 \lambda n:nat. (S O) < n \land
 285 (\forall m:nat. m \divides n \to (S O) < m \to  m = n).
 286
 287 theorem not_prime_O: \lnot (prime O).
 288 simplify.intro.elim H.apply not_le_Sn_O (S O) H1.
 289 qed.
 290
 291 theorem not_prime_SO: \lnot (prime (S O)).
 292 simplify.intro.elim H.apply not_le_Sn_n (S O) H1.
 293 qed.
 294
 295 (* smallest factor *)
 296 definition smallest_factor : nat \to nat \def
 297 \lambda n:nat.
 298 match n with
 299 [ O \Rightarrow O
 300 | (S p) \Rightarrow
 301   match p with
 302   [ O \Rightarrow (S O)
 303   | (S q) \Rightarrow min_aux q (S(S q)) (\lambda m.(eqb (mod (S(S q)) m) O))]].
 304
 305 (* it works !
 306 theorem example1 : smallest_prime_factor (S(S(S O))) = (S(S(S O))).
 307 normalize.reflexivity.
 308 qed.
 309
 310 theorem example2: smallest_prime_factor (S(S(S(S O)))) = (S(S O)).
 311 normalize.reflexivity.
 312 qed.
 313
 314 theorem example3 : smallest_prime_factor (S(S(S(S(S(S(S O))))))) = (S(S(S(S(S(S(S O))))))).
 315 simplify.reflexivity.
 316 qed. *)
 317
 318 theorem lt_SO_smallest_factor:
 319 \forall n:nat. (S O) < n \to (S O) < (smallest_factor n).
 320 intro.
 321 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
 322 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
 323 intros.
 324 change with
 325 S O < min_aux m1 (S(S m1)) (\lambda m.(eqb (mod (S(S m1)) m) O)).
 326 apply lt_to_le_to_lt ? (S (S O)).
 327 apply le_n (S(S O)).
 328 cut (S(S O)) = (S(S m1)) - m1.
 329 rewrite > Hcut.
 330 apply le_min_aux.
 331 apply sym_eq.apply plus_to_minus.apply le_S.apply le_n_Sn.
 332 rewrite < sym_plus.simplify.reflexivity.
 333 qed.
 334
 335 theorem lt_O_smallest_factor: \forall n:nat. O < n \to O < (smallest_factor n).
 336 intro.
 337 apply nat_case n.intro.apply False_ind.apply not_le_Sn_n O H.
 338 intro.apply nat_case m.intro.
 339 simplify.apply le_n.
 340 intros.apply trans_lt ? (S O).
 341 simplify. apply le_n.
 342 apply lt_SO_smallest_factor.simplify. apply le_S_S.
 343 apply le_S_S.apply le_O_n.
 344 qed.
 345
 346 theorem divides_smallest_factor_n :
 347 \forall n:nat. O < n \to smallest_factor n \divides n.
 348 intro.
 349 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O O H.
 350 intro.apply nat_case m.intro. simplify.
 351 apply witness ? ? (S O). simplify.reflexivity.
 352 intros.
 353 apply divides_b_true_to_divides.
 354 apply lt_O_smallest_factor ? H.
 355 change with
 356 eqb (mod (S(S m1)) (min_aux m1 (S(S m1))
 357   (\lambda m.(eqb (mod (S(S m1)) m) O)))) O = true.
 358 apply f_min_aux_true.
 359 apply ex_intro nat ? (S(S m1)).
 360 split.split.
 361 apply le_minus_m.apply le_n.
 362 rewrite > mod_n_n.reflexivity.
 363 apply trans_lt ? (S O).apply le_n (S O).simplify.
 364 apply le_S_S.apply le_S_S.apply le_O_n.
 365 qed.
 366
 367 theorem le_smallest_factor_n :
 368 \forall n:nat. smallest_factor n \le n.
 369 intro.apply nat_case n.simplify.reflexivity.
 370 intro.apply nat_case m.simplify.reflexivity.
 371 intro.apply divides_to_le.
 372 simplify.apply le_S_S.apply le_O_n.
 373 apply divides_smallest_factor_n.
 374 simplify.apply le_S_S.apply le_O_n.
 375 qed.
 376
 377 theorem lt_smallest_factor_to_not_divides: \forall n,i:nat.
 378 (S O) < n \to (S O) < i \to i < (smallest_factor n) \to i \ndivides n.
 379 intros 2.
 380 apply nat_case n.intro.apply False_ind.apply not_le_Sn_O (S O) H.
 381 intro.apply nat_case m.intro. apply False_ind.apply not_le_Sn_n (S O) H.
 382 intros.
 383 apply divides_b_false_to_not_divides.
 384 apply trans_lt O (S O).apply le_n (S O).assumption.
 385 change with (eqb (mod (S(S m1)) i) O) = false.
 386 apply lt_min_aux_to_false
 387 (\lambda i:nat.eqb (mod (S(S m1)) i) O) (S(S m1)) m1 i.
 388 cut (S(S O)) = (S(S m1)-m1).
 389 rewrite < Hcut.exact H1.
 390 apply sym_eq. apply plus_to_minus.
 391 apply le_S.apply le_n_Sn.
 392 rewrite < sym_plus.simplify.reflexivity.
 393 exact H2.
 394 qed.
 395
 396 theorem prime_smallest_factor_n :
 397 \forall n:nat. (S O) < n \to prime (smallest_factor n).
 398 intro. change with (S(S O)) \le n \to (S O) < (smallest_factor n) \land
 399 (\forall m:nat. m \divides smallest_factor n \to (S O) < m \to  m = (smallest_factor n)).
 400 intro.split.
 401 apply lt_SO_smallest_factor.assumption.
 402 intros.
 403 cut le m (smallest_factor n).
 404 elim le_to_or_lt_eq m (smallest_factor n) Hcut.
 405 absurd m \divides n.
 406 apply transitive_divides m (smallest_factor n).
 407 assumption.
 408 apply divides_smallest_factor_n.
 409 apply trans_lt ? (S O). simplify. apply le_n. exact H.
 410 apply lt_smallest_factor_to_not_divides.
 411 exact H.assumption.assumption.assumption.
 412 apply divides_to_le.
 413 apply trans_lt O (S O).
 414 apply le_n (S O).
 415 apply lt_SO_smallest_factor.
 416 exact H.
 417 assumption.
 418 qed.
 419
 420 theorem prime_to_smallest_factor: \forall n. prime n \to
 421 smallest_factor n = n.
 422 intro.apply nat_case n.intro.apply False_ind.apply not_prime_O H.
 423 intro.apply nat_case m.intro.apply False_ind.apply not_prime_SO H.
 424 intro.
 425 change with
 426 (S O) < (S(S m1)) \land
 427 (\forall m:nat. m \divides S(S m1) \to (S O) < m \to  m = (S(S m1))) \to
 428 smallest_factor (S(S m1)) = (S(S m1)).
 429 intro.elim H.apply H2.
 430 apply divides_smallest_factor_n.
 431 apply trans_lt ? (S O).simplify. apply le_n.assumption.
 432 apply lt_SO_smallest_factor.
 433 assumption.
 434 qed.
 435
 436 (* a number n > O is prime iff its smallest factor is n *)
 437 definition primeb \def \lambda n:nat.
 438 match n with
 439 [ O \Rightarrow false
 440 | (S p) \Rightarrow
 441   match p with
 442   [ O \Rightarrow false
 443   | (S q) \Rightarrow eqb (smallest_factor (S(S q))) (S(S q))]].
 444
 445 (* it works!
 446 theorem example4 : primeb (S(S(S O))) = true.
 447 normalize.reflexivity.
 448 qed.
 449
 450 theorem example5 : primeb (S(S(S(S(S(S O)))))) = false.
 451 normalize.reflexivity.
 452 qed.
 453
 454 theorem example6 : primeb (S(S(S(S((S(S(S(S(S(S(S O)))))))))))) = true.
 455 normalize.reflexivity.
 456 qed.
 457
 458 theorem example7 : primeb (S(S(S(S(S(S((S(S(S(S((S(S(S(S(S(S(S O))))))))))))))))))) = true.
 459 normalize.reflexivity.
 460 qed. *)
 461
 462 theorem primeb_to_Prop: \forall n.
 463 match primeb n with
 464 [ true \Rightarrow prime n
 465 | false \Rightarrow \lnot (prime n)].
 466 intro.
 467 apply nat_case n.simplify.intro.elim H.apply not_le_Sn_O (S O) H1.
 468 intro.apply nat_case m.simplify.intro.elim H.apply not_le_Sn_n (S O) H1.
 469 intro.
 470 change with
 471 match eqb (smallest_factor (S(S m1))) (S(S m1)) with
 472 [ true \Rightarrow prime (S(S m1))
 473 | false \Rightarrow \lnot (prime (S(S m1)))].
 474 apply eqb_elim (smallest_factor (S(S m1))) (S(S m1)).
 475 intro.change with prime (S(S m1)).
 476 rewrite < H.
 477 apply prime_smallest_factor_n.
 478 simplify.apply le_S_S.apply le_S_S.apply le_O_n.
 479 intro.change with \lnot (prime (S(S m1))).
 480 change with prime (S(S m1)) \to False.
 481 intro.apply H.
 482 apply prime_to_smallest_factor.
 483 assumption.
 484 qed.
 485
 486 theorem primeb_true_to_prime : \forall n:nat.
 487 primeb n = true \to prime n.
 488 intros.change with
 489 match true with
 490 [ true \Rightarrow prime n
 491 | false \Rightarrow \lnot (prime n)].
 492 rewrite < H.
 493 apply primeb_to_Prop.
 494 qed.
 495
 496 theorem primeb_false_to_not_prime : \forall n:nat.
 497 primeb n = false \to \lnot (prime n).
 498 intros.change with
 499 match false with
 500 [ true \Rightarrow prime n
 501 | false \Rightarrow \lnot (prime n)].
 502 rewrite < H.
 503 apply primeb_to_Prop.
 504 qed.
 505
 506 theorem decidable_prime : \forall n:nat.decidable (prime n).
 507 intro.change with (prime n) \lor \lnot (prime n).
 508 cut
 509 match primeb n with
 510 [ true \Rightarrow prime n
 511 | false \Rightarrow \lnot (prime n)] \to (prime n) \lor \lnot (prime n).
 512 apply Hcut.apply primeb_to_Prop.
 513 elim (primeb n).left.apply H.right.apply H.
 514 qed.
 515
 516 theorem prime_to_primeb_true: \forall n:nat.
 517 prime n \to primeb n = true.
 518 intros.
 519 cut match (primeb n) with
 520 [ true \Rightarrow prime n
 521 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = true).
 522 apply Hcut.apply primeb_to_Prop.
 523 elim primeb n.reflexivity.
 524 absurd (prime n).assumption.assumption.
 525 qed.
 526
 527 theorem not_prime_to_primeb_false: \forall n:nat.
 528 \lnot(prime n) \to primeb n = false.
 529 intros.
 530 cut match (primeb n) with
 531 [ true \Rightarrow prime n
 532 | false \Rightarrow \lnot (prime n)] \to ((primeb n) = false).
 533 apply Hcut.apply primeb_to_Prop.
 534 elim primeb n.
 535 absurd (prime n).assumption.assumption.
 536 reflexivity.
 537 qed.
 538