Skip to main content
3 of 5
added 1 character in body
J. W. Tanner
  • 64.6k
  • 5
  • 45
  • 89

Explain a section of Euclid's Theorem on an infinite number of prime numbers.

I'm trying to understand Euclid's Theorem, using reductio ad absurdum, which states:

There are an infinite number of prime numbers.

In the book it has the following explanation: We assume that there are a finite number of prime numbers, $p_1, p_2, ..., p_n$. We then consider an integer $Q$: $$Q:= p_1 \cdot p_2 \cdot ... \cdot p_n+1$$

From the Fundamental Theorem of Arithmetic we know that any composite number can be represented as the product of various prime numbers. Therefore:

$$Q=p_1^{e_1} \cdot p_2^{e_2} \cdot ...\cdot p_n^{e_n}, \ \ \text{for a suitable }e^1,...,e^n \in \mathbb{N_0}$$

Since $Q>1$, there is at least one $i \in [n]$ with $e^i \neq 0$. Therefore, for $p_i$ we have that:

$$p_i |Q \ \text{and} \ p_i | (Q-1)$$

This is a contradiction to our original assumption that $p_i \geq2$. Thus there are an infinite number of prime numbers.

I'm having difficulty understanding how the fact $p_i |Q \ \text{and} \ p_i | (Q-1)$ is used to come to the contradiction.

Ski Mask
  • 2k
  • 3
  • 16
  • 38