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