5
$\begingroup$

The following proof is from Introduction to Mathematics (Devlin). I am not trying to disprove Devlin or Euclid. I’m trying to understand if the questions my mind asks are unwarranted and why.

Statement: There are infinitely many prime numbers.

(Proof: First part) "The truth of this statement can be proved by an ingenious argument known to Euclid.1 The idea is to show that if we list the primes in increasing order as $p_1, p_2, p_3,..., p_n,...$ then the list must continue forever. (The first few members of the sequence are: $p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7, p_5 = 11$, and so on.) Consider the list up to some stage $n$: $p_1, p_2, p_3,..., p_n$ The goal is to show that there is another prime that can be added to the list. Provided we do this without assigning n a specific value, this will imply at once that the list is infinite.

Let $N$ be the number we get when we multiply together all the primes we have listed so far and then add $1$, i.e., $N = (p_1p_2\cdots p_n) + 1$ Obviously, $N$ is bigger than all the primes in our list, so if $N$ is prime, we know there is a prime bigger than $p_n$, and hence the list can be continued. (We are not saying that $N$ is that next prime. In fact, $N$ will be much bigger than $p_n$, so it is unlikely to be the next prime.)"

Q1) Why is the proof legit? This proof employs only on $N=(1…5)+1$. How, without calculating an answer for EVERY $p_X...p_N$, can one assume the proof will continue to be true?

Q2) How about if $N=(p1…p_\infty)+1$?

Q3) How can it be said “hence the list can be continued”?

$\endgroup$
  • 1
    $\begingroup$ if N is prime, we know there is a prime bigger than pn, and hence the list can be continued There must be an else part to that later on. Please quote enough of the proof that the question makes sense. $\endgroup$ – dxiv Nov 9 '16 at 4:40
  • 1
    $\begingroup$ Please use MathJax. For example, instead of p1 = 2 (giving "p1 = 2") write $p_1 = 2$ (giving $p_1 = 2$). That way it is much more readable. Also note that in MathJax, \infty gives $\infty$. $\endgroup$ – celtschk Nov 12 '16 at 9:42
  • $\begingroup$ What is $p_\infty$? $\endgroup$ – Carl Mummert Nov 21 '16 at 13:59
5
$\begingroup$

Q1 is the key. It is not just about the first five primes. It is saying that you suppose somebody claims they have a finite list that contains all the primes. You want to prove them wrong by showing there is at least one prime not on their list. You take all the primes on the list, multiply them, and add one. That is the $N$ here. None of the primes on the list can divide $N$, because they will all have a remainder $1$ when you do the division. Therefore either $N$ is prime (and is not on the list) or (and your summary missed this part) it is divisible by at least one prime, which is not on the list. In either case there is a prime not on the list. If your adversary adds this prime to the list, you repeat the calculation, finding $N'$ and another prime not on the list. This shows that any finite list cannot contain all the prime numbers.

Q2. pInfinity does not make sense, so we cannot compute this $N$. Multiplication is only defined with finitely many factors. We can compute limits of finite products that have more and more terms when the limit exists, but infinite products of numbers larger than $1$ diverge.

$\endgroup$
0
$\begingroup$

The write-up by Devlin conveys the idea of a proof (of infinitude of primes) in a way that reflects the limitations of what is found in Euclid.

Namely Euclid was writing long before a principle of "proof by induction" had been articulated. So from a modern perspective there is criticism of that original as being merely one example and not a rigorous treatment "for all $N$".

However the idea of the proof is so clear in Euclid that it makes for a very reasonable exercise for students to supply that lack of rigor.

$\endgroup$
0
$\begingroup$

This is an "indirect proof" or "proof by contradiction". If there were only a finite number of primes, say, $p_1$, $p_2$, ..., $p_n$ then we could multiply them all together and add 1: $p_1p_2...p_n+ 1$. That is not divisible by any of $p_1$, $p_2$,... $p_n$ since dividing by each leaves a remainder of 1. Therefore either it is prime or it is divisible by some prime not included in that list. Either way, we arrive a contradiction to the hypothesis that $p_1$, $p_2$, ... $p_n$ are the only prime. A true statement cannot lead to a statement contradicting itself so the original statement must be false.

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