Divisibility and factorization · Definition

Infinitude of primes

elementary number theorydivisibility and factorization

Before you start you need to know

Euclid showed that no finite list of primes can contain them all. The central idea is to build a number that escapes any given list.

Definition

The infinitude of primes is Euclid's theorem stating that the set of prime numbers is infinite: given any finite list of primes \(p_1,\dots,p_n\), there is a prime not on it.

\[p\mid p_1p_2\cdots p_n+1\ \Longrightarrow\ p\neq p_i\ \text{for all } i\]

If the primes were finite, we could list them as \(p_1, p_2, \dots, p_n\). Then the number \(N = p_1 p_2 \cdots p_n + 1\) is greater than 1 and, by the fundamental theorem of arithmetic, has at least one prime divisor.

Take the list 2, 3, 5, 7, 11, 13 and form \(N = 30031\). No prime in the list divides \(N\), since each leaves remainder 1. So \(N\) has a prime outside the list, contradicting the hypothesis.

A typical mistake is claiming that \(N = p_1 p_2 \cdots p_n + 1\) is always prime. For example, \(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59\cdot 509\), so the argument does not produce primes, only guarantees a new one.

Think about it

Why is \(N = p_1\cdots p_n + 1\) not always prime?

Because \(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59\cdot 509\), so it can be composite.

Exercises 10

  1. Which statement summarizes Euclid's theorem about primes?
  2. State the idea of Euclid's proof by contradiction.
  3. What number is constructed in Euclid's proof from the primes 2, 3 and 5?
  4. According to Euclid's argument, what property does \(N = p_1 p_2 \cdots p_n + 1\) have with respect to the primes in the list?
  5. Which statement about the list 2, 3, 5, 7 is correct?
  6. Compute \(N = 2\cdot 3\cdot 5\cdot 7\cdot 11 + 1\) and determine its smallest prime divisor.
  7. What is the remainder of \(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1\) when divided by \(7\)?
  8. If \(p_1,\dots,p_n\) are primes and \(N = p_1\cdots p_n + 1\), which statement about \(N\) is true?
  9. Using the list 2, 3, 5, 7, 11, what is the constructed number and a prime not in the list?
  10. Suppose \(p_1,\dots,p_n\) are all the primes. Explain why \(N = p_1\cdots p_n + 1\) yields a contradiction using the fundamental theorem of arithmetic.

What comes next

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 3
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 1