Proof of infinitely many primes, clarification

Proof:
The proof is by contradiction.
Suppose there are only finitely many primes.
Let the complete list be $p_1,p_2,\dots,p_n$.
Let $N = p_1p_2 \dots p_n+1$.
According to the Fundamental Theorem of Arithmetic, $N$ must be divisible by some prime.
This must be one of the primes in our list. Say $p_k \mid N$.
But $p_k\mid p_1\dots p_n$, so $p_k\mid(N-p_1 \dots p_n) = 1$
Hence contradiction.

I don't see how this proof works. I understand that $N$ isn't necessarily prime, but I don't understand how it apparently must show that some primes weren't in our list. A number could be made of different powers of the given primes right?

Someone please explain.

Solution 1:

Suppose that there are only $n$ primes. Let $p_1,p_2,p_3,\cdots,p_n$ be all the primes in the world. Let $N$ be the product of all these primes plus $1$, i.e. $N=p_1p_2 \cdots p_n+1$. We know that $N$ must be a product of primes. But the only primes in the world are $p_1,p_2,\cdots,p_n$. So one of these must be a factor of $N$. Since it doesn't matter which, let's say $p_1$ is a factor of $N$. Then we use $$ N=p_1p_2\cdots p_n +1 $$ to find that $$ N-p_1p_2\cdots p_n =1 $$ But $p_1$ divides the left side of the equality since $p_1$ is a factor of $N$ (from above) and it divides $p_1p_2\cdots p_n$ because it's part of the product.

But since it divides the left side it must divide the right side of the equality. But that means $p_1$ divides $1$. But that can't happen because $p_1$ has to be at least as big as $2$ - the smallest prime there is - and no number except $1$ and $-1$ divide $1$. Therefore, we have a contradiction. This means our assumption - that there are only $n$ primes, is wrong.

What we have done is used our primes $p_1,p_2,\cdots,p_n$ to make a number which needs a new prime not among the list $p_1,p_2,\cdots,p_n$. So for any $n$ primes you have, you can always make a number forcing you to need at least one more prime which lets you make another such number and so forth. So of course there are infinitely many primes.

Solution 2:

• We have a list of primes
• $N$ is divisible by a prime.
• None of the primes in the list divides $N$

Therefore...

• $N$ is divisible by a prime not on the list

and thus

• There is a prime not on the list

Solution 3:

This proof by contradiction is a badly organized proof. It should instead be done like this:

Suppose you have any finite set of primes $p_1,\ldots,p_n$. (DO NOT assume that there are no other primes.)

Then no prime factor of $(p_1\cdots p_n)+1$ can be one of the primes $p_1,\ldots,p_n$. (That part you can prove by contradiction without, as far as I know, introducing flaw into the proof that would not otherwise be there.)

Therefore there is at least one more prime than $p_1,\ldots,p_n$. No matter how many you've listed so far, there is at least one more. ${}\qquad\blacksquare$

That is how Euclid did it.

One of the problems of rearranging this into the frequently seen proof by contradiction is just that that adds an extra complication to the proof that serves no purpose, thereby making the proof appear more complicated than it really is.

Another problem is this: Some authors (e.g. G. H. Hardy (not related to me as far as I know)) say something along these lines: Because $(p_1\cdots p_n)+1$ is not divisble by any of the primes, it must itself be prime, and then we get a contradiction. Only the assumption that the list $p_1,\ldots,p_n$ contains all primes --- an assumption that is present only when this is rearranged into a proof by contradiction --- causes anyone to say that it is not divisible by any primes, and only that conclusion makes anyone say that therefore it is itself prime. This leads students to think mistakenly that it has been proved that if you multiply the first $n$ primes and then add $1$, the number you get is always prime. But that is false. And if a student then finds counterexamples (e.g. the six smallest primes) then the student may mistakenly conclude that the proof is simply wrong.

Another problem with preseting it as a proof by contradiction is that authors who do that often explicitly state that Euclid did it that way. That is historically false.

Catherine Woodgold and I wrote a joint paper, published in the Mathematical Intelligencer in fall 2009, debunking the false historical claims and demonstrating the superiority of Euclid's version over the proof by contradiction falsely attributed to Euclid.

And you shouldn't say "infinite primes" when you mean "infinitely many primes". "Infinite primes" would be primes each one of which is infinite. In colloquial speech the word "infinite" may be used that way, but in mathematical terminology it is an incorrect usage.