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

I'm trying to understand Euclid's Theorem, using proof by contradiction, 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, \dotsc, p_n$$. We then consider an integer $$Q$$: $$Q:= p_1 \cdot p_2 \dotsb 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} \dotsb p_n^{e_n}, \ \ \text{for a suitable }e_1,\dotsc,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 \mid Q \ \text{and} \ p_i \mid (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 \mid Q \ \text{and} \ p_i \mid (Q-1)$$ is used to come to the contradiction.

• If a number divides two other numbers, it also divides their differences. Jun 5, 2020 at 12:29

If $$p\mid Q$$ and $$p\mid(Q-1)$$, then $$p$$ is a factor of $$Q-(Q-1)=1$$. The only positive integer factor of $$1$$ is $$1$$.