3
$\begingroup$

I am interested in understand the proof of infinitely many primes. It seems like quite an easy proof, ( I know there are many but I am referring to the proof that goes as follows);

" Suppose there are only finitely many primes, lets say n of them, we can denote them as p1,p2,..,pn. Now we construct a new number P=(p1)(p2)..(pn)+1. Clearly P is larger than any of the primes, so it does not equal any one of them. Since p1,p2,,pn constitute all primes, P cannot be a prime. Thus it must be divisible by at least one of our finitely many primes, say pn. But when we divide P by Pn we get a remainder of 1 which is a contradiction. So our original assumption must be false."

I understand a lot of what it is saying, I am just not understanding where the +1 ties in. I see that if we assume P is not prime, and then cannot divide without a remainder there is a contradiction, but what if that +1 was not in the statement question originally?

I hope what I am asking makes sense to you guys,

Thanks a lot.

(Source for proof Hans Riesel, Prime Numbers and Computer Methods for Factorization, Birkhaeuser, 1985, ISBN 0-8176-3291-3.)

$\endgroup$
  • $\begingroup$ The +1 is what guarantees that $P$ is not divisible by any of our primes. Thus, there must be new primes which divide it that we didn't list already. $\endgroup$ – Alex G. Jun 9 '14 at 21:07
  • $\begingroup$ Adding $1$ to the product of the primes is what makes it coprime to all factors (all primes). It's a special case of $\,\gcd(n,n+1)= 1\,$ for $\,n = $ product of all primes. $\endgroup$ – Bill Dubuque Jun 9 '14 at 21:09
  • $\begingroup$ Without the $+1$, $P$ would be divisible by every known prime, rather than indivisible by them. $\endgroup$ – user2357112 Jun 9 '14 at 21:21
  • $\begingroup$ You can use $-1$ instead of $+1$ unless you have the single prime $2$ $\endgroup$ – Mark Bennet Jun 9 '14 at 21:36
  • $\begingroup$ As I just noted in an answer this evening, this widespread way of proving the infinitude of primes is inferior to the one that Euclid wrote and is frequently incorrectly reported to be what Euclid wrote. Some of the best mathematicians are guilty of this error. math.stackexchange.com/questions/842187/… $\endgroup$ – Michael Hardy Jun 21 '14 at 4:29
2
$\begingroup$

The key idea is that we can generate an integer coprime to any finite set of integers by taking their product, then adding $\,{\bf\color{#c00}1}.\,$ Therefore, iterating this method we can generate an infinite sequence $\ 2,\,3,\,7,43,\ \ldots,\ \color{#0a0}{f_{n}} = \,\color{#c00}{\bf 1} + f_1\cdots f_{n-1}$ of coprimes, i.e. $\,{\rm gcd}(f_n,f_k) = 1\,$ if $\,n>k,$ since any common divisor of $\,\color{#0a0}{f_n},\,\color{#c0e}{f_k}\,$ divides $\, \color{#c00}{\bf 1} = \color{#0a0}{f_n} - f_1\cdots \color{#c0e}{f_k}\cdots f_{n-1}.$

Any infinite sequence $\,f_n > 1 \,$ of coprimes yields an infinite sequence of distinct primes $\, p_n $ obtained by choosing $\,p_n$ to be any prime factor of $\,f_n,\,$ e.g. the least factor $> 1.$

Remark $\ $ A shorter variant of Euclid's proof arises by noting that iterating the map $\, n\mapsto n^2\!+n$ generates integers with an unbounded number of prime factors, because $\,n(n+1)\,$ includes all prime factors of $\,n\,$ plus some (new!) prime factor of $\,n+1,\,$ since $\,n\,$ and $\,n+1\,$ are coprime.

$\endgroup$
  • 2
    $\begingroup$ I think that this answer provides insight into what is really going on here. The remark is well worth noting [the first time I have noted it] . I can't see a reason for a down vote - much better to understand this answer or to ask about any confusion so it can be clarified. $\endgroup$ – Mark Bennet Jun 9 '14 at 21:58
  • $\begingroup$ @Mark There have been many perplexing downvotes recently. I wish the (serial?) downvoter would explain what is viewed as problematic so that the answer can be improved, e.g. eliminating points that may be unclear, etc. Constructive feedback is always welcome. $\endgroup$ – Bill Dubuque Jun 9 '14 at 22:03
1
$\begingroup$

If the +1 were not there, then P would be composite, and we wouldn't know whether there was another prime beyond pn. This way, we're guaranteed that there is one:

With the +1, either

  1. P is composite, the product of primes other than the pi in the list (since it's definitely not divisible by any prime in the list) - contradicting our assumption about the pi; or
  2. P is itself a prime; but it's not in the list - again a contradiction.

Without the +1, P is definitely composite, and the product of primes in the list - which doesn't let us conclude anything about primes that may not be in the list.

$\endgroup$
0
$\begingroup$

An almost identical question was posted here in recent hours. Here is the answer I posted.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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