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

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

• Either $Q$ is prime or not. If it is prime, it is not in the "primes list" because it is greater than every prime in the list. Thus, $Q$ is not prime and hence must have a prime factor: but all primes are in the list (by assumption) and thus some of them must divide $Q$. Mar 16, 2018 at 15:26
• To @MauroALLEGRANZA: But how did you know it's greater than every prime in the list? Mar 16, 2018 at 15:35
• Because is the product of them all plus 1 ! Mar 16, 2018 at 15:40
• Ugh. This book proof is everything I hate about logic introductions. 1) The Fundamental Theorem of Arithmetic is overkill. 2) This isn't a proof by contradiction but a proof of the negation: "the set of primes is not finite". 3) We could view this as a proof by contradiction of "you aren't unable to extend any finite list of primes", but it actually constructively proves the direct statement, perhaps worded "the set of all primes is more numerous than any assigned multitude of primes", so a proof by contradiction is silly. 4) As you probably guessed, the quoted statement is from Elements. Mar 16, 2018 at 20:49
• As far as I can tell, your issues with the given proof have to do with number-theoretic concerns which is consistent with the focus of all the answers. My comment does not address those issues which is why I didn't make it an answer. The motivation for my comment is annoyance (directed at the book) with the (very probable) confusion about "proof by contradiction" it is sowing and the subtle misrepresentation of classical (as in old) theorems and proofs. Mar 17, 2018 at 2:13

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

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

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

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.