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.
$\endgroup$ 88 Answers
$\begingroup$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.
$\endgroup$ 9 $\begingroup$- 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
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.
$\endgroup$ 5 $\begingroup$Hint $\ $ Consecutive integers are always coprime: $\, d\mid N,N\!-\!1\,\Rightarrow\, d\mid N-(N\!-\!1) = 1.$
Thus $\,N\,$ is coprime to $\,N\!-\!1 = p_1\cdots p_n\,$ so $\,N\,$ is not divisible by any of the primes $\,p_i.$
But $\,N>1\,$ so it has some prime factor $\,p.\,$ By above $\,p\,$ is a "new" prime, not among the $\,p_i.$
Remark $\ $ Euclid's proof was constructive like the above, i.e. not by contradiction.
$\endgroup$ $\begingroup$$p_1$ can't divide $N=p_1(\cdots)+1$ since if you divide $N$ by $p_1$ you get a remainder of 1. The same holds for each of the primes so none can divide $N$, hence there is some other prime.
$\endgroup$ $\begingroup$Here is another idea to prove this statement. Our instructor attributed to the french mathematician Hermite. The proof goes as follows:
$\endgroup$ 4 $\begingroup$for a given integer $n$. Let $q_n$ be the greatest prime factor of $n! +1$. We claim that $q_n > n$. If not so, then clearly $q_n | n! $ and by construction $q_n|(n! + 1)$, consequently $q_n|1$. Which is impossible, a contradiction reached. It follows that always there exists a prime number $q_n$ greater than $n$ for any integer $n$ as required.
Can this be considered a proof? why or why not
Let's say the last prime number we know is Pn, then there has to exist a prime number Pn+1 because Pn * Pn+1 results to a number N whose prime factorisation is Pn and Pn+1. Since numbers are infinite, N exists and so does Pn and Pn+1
In this case, I assume there will be a superior prime, which if every prime existed is odd, then there exist $k+1$ if there exist $2k+1$, for some $k$ of course.
The proof seems not by contradiction, but by superiority, assuming that all products by prime is prime, in this case, $N+1$ that is divisible by prime number, which is false. Since, there will always a reminder of 1, the proof seems to be flawed.
However, if you consider that, every prime number is odd, in this case, $（2k+1）$ for $N$, and I will prove in this way,
$N = （2k+1）* （2k+1） .... + 1$ for some prime numbers, which lead to the factor of 2, and thus, leading it into the divisibility of 2, thus, reducing it to k+1 for some primes, that for me already proved, all primes are odd when $>2$, which $2k+1$, and have the smallest prime of 2, when $k+1$. Since, k, is some numbers that satisfy prime, k cannot be an empty set. It proves that k+1 and 2k+1, is uniquely existed, thus, k cannot be zero. Thank you
$\endgroup$
