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?