Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
A small point. Euclid's actual proof is not by contradiction. It says: Given any (finite) list of primes, to construct a prime not in that list. –  GEdgar Jun 21 at 1:34
2  
For some people, proof by contradiction is a capital sin, hence they rush to defend the honor of a long dead mathematician. What I don't like about the proof as it was presented to you is that it has the proof of the fundamental theorem of arithmetic as a prerequisite. If I was a teacher, I'd present the fundamental theorem of arithmetic after this one. –  Robert Soupe Jun 21 at 1:53
4  
@Robert The proof does not use FTA, only the Lemma that every natural $> 1$ has a prime factor, which has a very simple proof by induction. A direct proof is preferred not only because it is constructive, but also because it is far less confusing to beginners, who frequently become hopelessly confused reasoning in hypothetical structures such as "$\Bbb Z$ with only finitely many primes". This proof by contradiction is one of the major sources of confusion in general level math forums (there were thousands of posts about such on sci.math). –  Bill Dubuque Jun 21 at 2:38
    
@RobertSoupe : I do not consider proof by contradiction wrong, but I consider it wrong to make this proof into a proof by contradiction, for reasons set forth in my answer below and in my published work on this proof. –  Michael Hardy Jun 21 at 2:48
    
BTW I agree that uniqueness of prime factorizations is not needed in this argument. Existence, on the other hand, is needed, of course. –  Michael Hardy Jun 21 at 2:53

5 Answers 5

up vote 10 down vote accepted

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.

share|improve this answer
    
To understand the other two answers, I needed to have read your answer, so I suppose that makes your answer the best answer. Thank you for the long post, I understand now. –  Exam in 5 days Jun 21 at 1:30
2  
No, the primes are not infinite; rather the set of all primes is infinite. There is not one infinite prime among them, much less is it the case that all of them are infinite. At any rate this is an inferior proof. The way Euclid proved it, which was not by contradiction, is superior. –  Michael Hardy Jun 21 at 2:49
    
No problem. @MichaelHardy Thank you for correcting my loose language. When I said the primes are infinite, of course I was being colloquial and meant the set of all prime numbers. And I agree. Euclid's original constructive proof is simple and more informative than the proof by contradiction which changes little of his original proof. I can think of no other reason of why it's commonly taught other than someone thought of it once as an early-on example of proof by contradiction and people just stuck with it. Why they don't just stick with the irrationality of $\sqrt{2}$ is beyond me. –  mathematics2x2life Jun 21 at 19:09
    
@mathematics2x2life Can I just clarify what you meant by "Why they don't just stick with the irrationality of $\sqrt{2}$ is beyond me." Were you saying that they should use this as the primary example of proof by contradiction, or that $\sqrt{2}$ is somehow related to proving infinite primes. Second question: Why is proof by contradiction so ill-spoken? What makes it such a bad form of proof? –  Exam in 5 days Jun 22 at 7:45
    
@Examin5days The irrationality of $\sqrt{2}$ is often the introductory example to proof by contradiction and is a good, simple example. While proving the set of primes is infinite by contradiction is fine, it is unnecessary. Notice we can remove the assumption that the primes are finite and just assume there are $n$ of them. With the discussion above, we show using these $n$ primes we can make a number which needs a new prime not among those $n$, so there are at least $n+1$ primes. So the set of primes is infinite - no need for the contradiction. –  mathematics2x2life Jun 22 at 21:43
  • 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
share|improve this answer

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.

share|improve this answer
1  
All of that (and more!) was done long before said paper was published in many diverse threads on sci.math (some of which M.H. participated in). –  Bill Dubuque Jun 21 at 3:47

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.