1
$\begingroup$

Here's Euclid's proof of Infinitude of Primes in Rosen's Discrete Mathematics:

We will prove this theorem using a proof by contradiction. We assume that there are only finitely many primes, $p_1, p_2,..., p_n$. Let

$$Q = p_1p_2...p_n +1$$

By the fundamental theorem of arithmetic, $Q$ is prime or else it can be written as the product of two or more primes. However, none of the primes $p_j$ divides $Q$, for if $p_j |Q$, then $p_j$ divides $Q-p_1p_2...p_n =1$

.....
.....
.....

Which kind of logic is that (the bolded part)? If I accept it, the proof looks straightforward as a composite integer needs to be divided by primes. So, it's a contradiction. But, I have trouble understanding the bolded part. Which basic theorem can help me here?

$\endgroup$
0
$\begingroup$

So if $p_j|Q$ then $Q=p_jq$ for some integer $Q$.

Looking at $Q-p_1p_2...p_j...p_n=p_j(q-p_1p_2...p_n)=1$ you see that there is a factor $p_j$ on the left-hand side times another integer, so $p_j$ would have to divide $1$. That is a contradiction, so no such $p_j$ can exist.

$\endgroup$
2
$\begingroup$

Suppose $Q=p_j \cdot N$ for a natural number $N$. Then $$Q- p_1p_2 ..p_{j-1}p_jp_{j+1}.. p_n = p_j(N-p_1p_2..p_{j-1}p_{j+1}..p_n)$$ and $p_j$ divides $Q-p_1..p_n$, but this is the number $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.