This site is supported by donations to The OEIS Foundation.

Euclid's proof that there are infinitely many primes

From OeisWiki

Jump to: navigation, search

After centuries, Euclid's proof of the following theorem remains a classic, not just for proving this particular theorem, but as a proof in general.

Theorem. There are infinitely many primes.

Proof (Euclid). Given a finite number of primes \scriptstyle p_1,\, \ldots,\, p_\text{max}, \, compute the product of the primes
N = \prod_{i = 1}^\text{max} p_i \,
It is obvious that \scriptstyle N + 1 \, is not divisible by any of the primes that exist, the remainder being 1 in all cases. So either \scriptstyle N + 1 \, 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 \scriptstyle \mathbb{P} \, the set of all prime numbers. Since 2 is prime, \scriptstyle \mathbb{P} \, is not the empty set. We will now demonstrate that there is no finite subset \scriptstyle Q \, of \scriptstyle \mathbb{P} \, which exhausts \scriptstyle \mathbb{P} \,. Let's designate the elements of the non-empty subset \scriptstyle Q \, as \scriptstyle q_1, \ldots q_{len} \, then compute \scriptstyle m \,=\, 1 + \prod_{i = 1}^{len} q_i \,. The "fundamental theorem of arithmetic" implies there is a prime \scriptstyle p \, which divides \scriptstyle m \,. Since no \scriptstyle q_i \, divides \scriptstyle m \,, it follows that \scriptstyle p \,\notin\, Q \, and \scriptstyle Q \,\neq\, \mathbb{P} \,. Therefore, \scriptstyle \mathbb{P} \, is infinite.[1] □

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 \scriptstyle p_{max} \,=\, 5 \,, we have \scriptstyle N \,=\, 30 \,

File:Euclid30 Graph.png

and \scriptstyle N + 1 \,=\, 31 \,, which is prime, and much larger than 5. We could work out on the number line an example in which \scriptstyle N + 1 \, is composite (with a prime factor greater than \scriptstyle p_{max} \,) but the dots for the prime factors of \scriptstyle N \, would be crowded too close together to be useful as an illustration.

The numbers \scriptstyle N + 1 \, for \scriptstyle max \,=\, 0 \, forward are sometimes called the "Euclid numbers" (see A006862.) The numbers \scriptstyle N \, 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 \scriptstyle n \,th Euclid number, see A051342.

Factorials (A000142) are sometimes used rather than primorials in the proof;[2] 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,

File:Euclid114 Graph.png

the prime factorization of \scriptstyle N + 1 \, would then reveal a prime we skipped over as well as a prime larger than the prime we declared to be the largest.

File:Euclid114 Graph wNewFactorWarn.png

Euclid's proof suggested the following sequences (A005265 and A005266) to Neil Sloane and other mathematicians, defined by the following recurrence relation:

a_1 = 3 \,
b_n = \prod_{k = 1}^n a_k \,

and \scriptstyle a_{n + 1} \, is the smallest prime factor (for A005265) or largest prime factor (for A005266) of \scriptstyle b_{n - 1} \,.

Notes

  1. ↑ Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications (1969, reprinted 2007): p. 6, Theorem 5.1
  2. ↑ 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.)

References

  • 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.
Retrieved from "http://oeis.org/wiki/Euclid%27s_proof_that_there_are_infinitely_many_primes"
Personal tools