Proof of infinitely many prime numbers

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

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

Solution 3:

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.