Here's the proof from the book I'm reading that proves there are infinitely many primes:
We want to show that it is not the case that there only finitely many primes. Suppose there are finitely many primes. We shall show that this assumption leads to a contradiction. Let $p_1, p_2,…,p_n$ be all the primes there are. Let $x = p_1…p_n$ be their product and let $y=x+1$. Then $y \in \mathbb{N}$ and $y \neq 1$, so there is a prime $q$ such that $q \mid y$. Now $q$ must be one of $p_1,…,p_n$ since these are all primes that there are. Hence $q \mid x$. Since $q \mid y$ and $q \mid x$, $q \mid (y-x)$. But $y-x=1$. Thus $q \mid 1$. But since $q$ is prime, $q \geq 2$. Hence $q$ does not divide 1. Thus we have reached a contradiction. Hence our assumption that there are only finitely many primes must be wrong. Therefore there must be infinitely many primes.
I have a couple of questions/comments regarding this proof. I will use a simple example to help illustrate my questions:
Suppose only 6 primes exist: $2, 3, 5, 7, 11, 13$
Let $x = p_1p_2p_3p_4p_5p_6=30,030$
Let $y = x + 1 = 30,030+1 = 30,031$
Questions/Comments:
-
The proof states there is a prime $q$ such that $q \mid y$ and that $q$ must be either $p_1, p_2, p_3, p_4, p_5,$ or $p_6$. However, none of the 6 primes listed, $(2,3,5,7,11,13)$, divides $30,031$. In fact, the only divisors for $30,031$ are $1, 59, 509$ and $30,031$. Doesn't the proof then break down here since there is no prime $q$ that divides $y$?
-
The prime factorization of $30,031$ is $59 \times 509$. These two numbers are factors of $30,031$ and are in fact primes themselves since they are only divisible by themselves or by 1. Have I shown that there exists $\gt 6$ primes? If so, what can I conclude now that I have shown this?
-
I don't understand why the contradiction $q$ divides $1$ and $q$ does not divide $1$ lead us to the assumption that the finitely many primes must be wrong. I understand how we reached the contradiction. I don't understand why contradiction leads us to the conclusion shows that are assumption that there is only finitely many primes is wrong.
My apologies for the long post. Thanks for any and all help.
Best Answer
This is an excellent example of a proof that is traditionally phrased as a proof by contradiction but is much better understood constructively. From a constructive viewpoint, the proof shows that given any list of primes $p_1, \ldots, p_n$ there is a prime $q$ (any prime divisor of $p_1p_2\ldots p_n + 1$) that is distinct from each $p_i$. So given any finite set of primes we can find a prime that is not in that set.