# Euclid's proof of Infinitude of Primes: If a prime divides an integer, why would it have to divide 1?

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?

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