Can't understand the logical structure of Euclid's infinitely many primes proof in Rosen's book.

Question

I'm reading the book Discrete Mathematics and It's Applications written by Rosen. At page 260, there is a proof using the technique similar to Euclid's. The following is my trying to understand the proof.

---

Assume that there are only finitely many primes, $p_1, p_2, ..., p_n$, I'll call it prime list later on. Let

$$Q = p_1p_2\cdots 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.

Let $p_j$ be an arbitrary prime in the prime list. Then $p_j$ can't divide $Q$, since:

1. If $p_j \mid Q$, then $p_j \mid (Q - p_1p_2\cdots p_n=1)$:

   The is because $p_j \mid (p_1p_2\cdots p_n)$, so $p_j \mid (1\cdot Q+(-1)\cdot(p_1p_2\cdots p_n))$.

2. Since $p_j \mid (Q - p_1p_2\cdots p_n=1)$ is false, $p_j \not\mid Q$:

   The only integer which divides all integer is $1$, but $p_j$ is a prime.

Since $p_j \not\mid Q$ also means that $Q$ is not $p_j$, $Q$ is not in the prime list. And since there is no prime in the prime list divides $Q$, $Q$ can't be written as the product of two or more primes. Finally, $Q$ has to be a prime, which is not in the prime list. We've arrived a contradiction.

---

I'm not sure whether it's correct, but that's how I understand the proof. And the following is the proof in my book:

I don't understand why it arrives the conclusion "Hence, there is a prime not in the list".

Please give me some hints...

Answer 1

The statement "$Q$ is prime or else it can be written as a product of two or more primes" implies there exists a prime dividing $Q$. Since none of the $p_j$ have this property, there has to be another prime not in the list which divides $Q$.

Answer 2

Let $p_j$ be a prime dividing $Q=p_1p_2\ldots p_n+1$. If $p_j$ is a prime in the list $p_1,p_2,\ldots,p_n$, then $p_j\mid Q-1$.

This means that there is some integer $k$ such that $Q=p_jk$ and some other integer $m$ such that $Q-1=p_jm$. Subtracting these two gives: $$1=Q-(Q-1)=p_j(k-m)$$ So $p_j$ divides $1$, but $p_j>1$, which is impossible

Answer 3

If $p$ is a prime number such that $p\mid Q$ then, since $Q-p_1p_2\ldots p_n=1$, $p\notin\{p_1,p_2,\ldots,p_n\}$ because otherwise $p\mid1$.

Answer 4

I was going through checking it by arbitrary number.
Let's $Q= 9699691$ be the prime number because as stated above none of $p_j$ (i.e $2$ to $19$ prime numbers) divides $Q$ which can be represented as $Q= 2\times3\times5\times7\times11\times13\times17\times19+1$ which must be prime number.
But $Q = 9699691=347\times27953$ which is a composite number. The thing is that the statement "$Q$ is prime or else it can be written as a product of two or more primes" implies there exists a prime dividing $Q$ but it ain't at our list. Since none of the $p_j$ have this property, there has to be another prime not in the list which divides $Q$.. which is why $347$, $27953$ does... both are primes.

Hope, this clarifies everything.