Proof of infinitely many prime numbers

Question

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:

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

2. 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?

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

Answer 1

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.

Answer 2

1. The proof does break down in a sense. You have reached a contradiction, which means the hypothesis that there are finitely many primes can not possibly be true.

2. So you thought you had 6 primes, you found 2 extra. Can you just add these two to your list and get all of the primes? If you repeat the process on these 8 primes, you will find that you will have even MORE primes by considering the product + 1. You can keep going and going and you will never run out of primes. This is the idea of the proof. It uses contradiction because you can do it all in one step and avoid the potential issue of doing the process infinitely many times.

Answer 3

Point 1: It's a theorem that any natural number $n>1$ has a prime factor. The proof is easy: for any number $n>1$, the smallest natural number $a>1$ which divides $n$ is prime (if it were not prime, it would not be the smallest).

Point 2: Yes, you have proved there are more than six primes. So what? The proof by contradiction doesn't suppose there are only six, but that there are a finite number of them.

Point 3: Actually, it's not really a proof by contradiction stricto sensu. It is proved that any finite list of primes in incomplete.

Answer 4

Here is a non-mathematical approach to the logic behind the proof by contradiction...

Suppose your assumption is that a suspect in a brutal murder is innocent because he said he couldn't have been at the location the person was murdered. You feel as though he is possibly telling the truth, but what you do know is that there are 5 other suspects. You know with 100% certainty due to the detail of the case there can't be anymore than 5 other suspects via proven information. But, the police can verify using obvious physical evidence such as video cameras that the 5 suspects could not possibly be guilty. Then there is either another suspect or the one assumed innocent is guilty. But we said that it was impossible for any other suspects to be considered. Therefore our original suspect is guilty.

This is exactly what is happening in a proof by contradiction.

Answer 5

You ask in #1 if the proof breaks down. No. What breaks down is the assumption that there are no more primes. You assumed you had a complete list of primes. Then you constructed a number that is not divisible by any of the primes in your list. Only two possibilities remain: Either the number you constructed is prime, or it is divisible by a number that is not in your list. Either way your list is not complete, which contradicts your initial assumption.

Simpy put, you assumed you had a complete list and by using that assumption you proved that the list was not complete. The assumption must therefore be wrong.

The answer to #3 is basically the same. By finding a contradiction when you made an assumption, you proved the assumption to be incorrect.

The answer to #2 is no, you did not prove you anything by noting that 59 and 509 are both prime. You are trying to prove that there is a finite list of primes. If you choose a particular set of primes as you did {2, 3, 5, 7, 11, 13} and show that that particular set doesn't hold all the primes, a skeptic would just say that you need to add more primes (like 59 and 509) because you didn't make your set big enough. The proof has to be more general which is why it doesn't say how many primes are in the finite set. The proof is written so that it works no matter how big the finite set is.

Answer 6

Suppose only 6 primes exist: 2,3,5,7,11,13

However, none of the 6 primes listed, (2,3,5,7,11,13), divides 30,031.

Then we already have a contradiction. Since there are only 6 primes (we supposed that at the beginning) and none of them divide 30,031, then 30,031 must be prime. However, 30,031 is not one of the only 6 primes that exist. So 30,031 cannot be prime, yet it must be prime.

So the proof works. In fact, it works precisely the same regardless of what set of numbers we suppose are the only primes that exist. Thus no finite set of numbers can include all the primes that exist. Thus there are an infinite number of primes.

Answer 7

The proof is essentially overexplaining. The point of contradiction would have been much clearer if the author had:

1. Reached it earlier.
2. Introduced less notation.

Since $p_1\cdots p_n+1$ cannot have any of $p_1,...,p_n$ as a prime factor we already have a contradiction.

The rest is just explaining to death why $p_1,...,p_n$ cannot be prime factors of $y=p_1\cdots p_n+1$ which should be clear since $y$ is $1$ off from being a multiple of either of those primes.

Answer 8

1. Well... yes... it does break down. You assumed that there are only 6 primes and reached a contradiction. You've successfully proved that there aren't only 6 primes.
2. Under the assumption that there are only 6 primes 30,031 isn't factorizable.
3. In proof by contradiction you prove proposition A by assuming A is not true, and through a series of logical steps reach an impossibility, thus proving that A must be true. Concurrently, in this proof, we assumed there is a finite number of primes. After a series of logical inferences we reached a contradiction. Since the only assumption we made in the process is that there are a finite number of primes, that assumption must be wrong.

Answer 9

1. Either $ 6 $ primes you considered are not all the primes, or $ 30031 $ is a new prime. Either way assumption is false. Proof by contradiction.
2. No, you haven't shown that two more primes exist. In this example yes, but not in general
3. Again, based on your assumption you reached something impossible that $q $ divides $ 1$. There is no such $q $ except $1$.

Start with $ 2,3,5 $ being the only prime numbers. Then you would have $ 31 $ as the new number. $ 2,3,5 $ do not divide $ 31$. But unlike your case, $31$ is a prime number. So the assumption is wrong.

Answer 10

Another way to arrive at a contradiction from your initial set-up is related to Rob Arthan's answer.

---

Given some arbitrary finite set of primes, say $\{p_1, p_2, ..., p_k\}$, define $N$ to be 1 more than their product, namely $$N = p_1 p_2 ... p_k\ + 1.$$

Now every positive integer is uniquely determined (up to ordering) by its prime divisors, and so $N$ must have at least one prime divisor, say $q$.

But $q$ cannot be one of the $p_i$s: if it was, then it would divide $N$ (which we just deduced) and also $p_1p_2...p_k$ (because $q$ is one of the $p_i$s). But then if $q$ divides $N$ and $N+1$, it must also divide their difference, $N - p_ 1p_2...p_k = 1$. This is a contradiction (since 1 is the empty product and does not have any prime divisors) and so $q$ must be a prime not in the finite set $\{p_1, p_2, ..., p_k\}$.

But the finite set we started with was arbitrary! This means that in any finite set of primes there exists an integer (one of the same form as $N$), at least one of whose prime divisors is not in that set. We conclude that there must be infinitely many primes.