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.
Best Answer
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.