1
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.