Content
Courant & Robbins Supplement to Chapter 1 "The Theory of Numbers" [p. 21 - 51]
There are infinitely many primes (proof by contradiction, first due to Euclid). This leads to a recursive approach for generating prime numbers (each new prime is the product of the previous primes plus 1.)
Start with the prime number p1 = 2 and p2 = 3.
Then the number p1p2 + 1 is either a prime or contains as a factor a prime which differs from those already found.
p1p2 + 1 = 2 . 3 +1 = 7 Therefore p3 = 7
Now consider 2 . 3 . 7 + 1 = 42 +1 = 43 This is also a prime. (Verified by Mathematica).
Therefore p4 = 43.
Now consider 2 . 3 . 7 . 43 + 1 = 42 . 43 + 1 = 1806 + 1 = 1807 This is not a prime number. It contains the two factors 13 and 139. 13 is a new prime and may now be added to the list.
Now consider 2 . 3 . 7 . 13 . 43 + 1 = 42 . 43 . 13 + 1 = 1806 . 13 + 1 = 23478 + 1 = 23479. This is not a prime number, but contains the two prime factors 53 and 543. 53 is a new prime and may be added to the list.
Now consider 2 . 3 . 7 . 13 . 43. 53 + 1 = 1806 . 53 + 1 = 95718 + 1 = 95719. This contains the three prime factors 13, 37 and 199, the latter two being new.
Here is the accompanying Mathematica notebook (web, Mathematica).
This is a very good feeling, as I knew there was something wrong, and I tracked the difficulty to a misunderstanding on my part of how the algorithm worked.
Although the algorithm works, I am not too impressed with it, as it involves a lot of work (if one doesn't have Mathematica to determine the prime factorization of a large number). |
