This site is supported by donations to The OEIS Foundation.
Euclid's proof that there are infinitely many primes
Theorem. There are infinitely many primes.
Proof (Euclid). Given a finite number of primes compute the product of the primes
It is obvious that is not divisible by any of the primes that exist, the remainder being 1 in all cases. So either is prime or is a composite with its prime factors not on the list. Either way, we have at least one new prime. □
This classic proof can be dressed up in many guises. For example:
Proof (Euclid-Bolker) Designate by the set of all prime numbers. Since 2 is prime, is not the empty set. We will now demonstrate that there is no finite subset of which exhausts . Let's designate the elements of the non-empty subset as then compute . The "fundamental theorem of arithmetic" implies there is a prime which divides . Since no divides , it follows that and . Therefore, is infinite. □
Of course in this version it is necessary to prove the fundamental theorem of arithmetic first.
Since Euclid viewed numbers primarily as geometric constructs, it is appropriate to work out a couple of examples on the number line. With , we have
and , which is prime, and much larger than 5. We could work out on the number line an example in which is composite (with a prime factor greater than ) but the dots for the prime factors of would be crowded too close together to be useful as an illustration.
The numbers for forward are sometimes called the "Euclid numbers" (see A006862.) The numbers are the primorials; see A002110. The Euclid numbers that are prime are listed in A018239 as "primorial primes." For the smallest prime factor of the th Euclid number, see A051342.
Factorials (A000142) are sometimes used rather than primorials in the proof; their disadvantage is that they grow much faster on account of the many repeated factors (especially 2), though in all fairness, the primorials also quickly grow beyond the range for which a typical calculator can show in full precision.
Euclid's proof even works if in our assumed finite list of primes we skip some of the smaller primes. If we were to say, for example, that 2, 3 and 19 are the only primes,
the prime factorization of would then reveal a prime we skipped over as well as a prime larger than the prime we declared to be the largest.
- ↑ Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications (1969, reprinted 2007): p. 6, Theorem 5.1
- ↑ As for example John Derbyshire, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. Washington, D.C.: Joseph Henry Press (2003) p. 34. (where the example given is 5! + 1.)
- H. Davenport, The Higher Arithmetic, 6th Ed. Cambridge University Press (1992): pp. 17–18.
- Benjamin Fine and Gerhard Rosenberger, Number Theory: An Introduction via the Distribution of Primes, Boston: Birkhäuser (2007) pp. 16–17, Theorem 2.3.1.
- Thomas Koshy, Elementary Number Theory with Applications, Harcourt Academic Press (2002): p. 100, Theorem 2.10.
- Paulo Ribenboim, The Little Book of Bigger Primes, Second Edition. New York: Springer Verlag (2004) p. 3.
- Michael Hardy and Catherine Woodgold, "Prime simplicity," The Mathematical Intelligencer, 31:4, pp. 44–52.