12
$\begingroup$

Here's the proof from the book I'm reading that proves there are infinitely many primes:

We want to show that it is not the case that there only finitely many primes. Suppose there are finitely many primes. We shall show that this assumption leads to a contradiction. Let $p_1, p_2,...,p_n$ be all the primes there are. Let $x = p_1...p_n$ be their product and let $y=x+1$. Then $y \in \mathbb{N}$ and $y \neq 1$, so there is a prime $q$ such that $q \mid y$. Now $q$ must be one of $p_1,...,p_n$ since these are all primes that there are. Hence $q \mid x$. Since $q \mid y$ and $q \mid x$, $q \mid (y-x)$. But $y-x=1$. Thus $q \mid 1$. But since $q$ is prime, $q \geq 2$. Hence $q$ does not divide 1. Thus we have reached a contradiction. Hence our assumption that there are only finitely many primes must be wrong. Therefore there must be infinitely many primes.

I have a couple of questions/comments regarding this proof. I will use a simple example to help illustrate my questions:

Suppose only 6 primes exist: $2, 3, 5, 7, 11, 13$

Let $x = p_1p_2p_3p_4p_5p_6=30,030$

Let $y = x + 1 = 30,030+1 = 30,031$

Questions/Comments:

  1. The proof states there is a prime $q$ such that $q \mid y$ and that $q$ must be either $p_1, p_2, p_3, p_4, p_5,$ or $p_6$. However, none of the 6 primes listed, $(2,3,5,7,11,13)$, divides $30,031$. In fact, the only divisors for $30,031$ are $1, 59, 509$ and $30,031$. Doesn't the proof then break down here since there is no prime $q$ that divides $y$?

  2. The prime factorization of $30,031$ is $59 \times 509$. These two numbers are factors of $30,031$ and are in fact primes themselves since they are only divisible by themselves or by 1. Have I shown that there exists $\gt 6$ primes? If so, what can I conclude now that I have shown this?

  3. I don't understand why the contradiction $q$ divides $1$ and $q$ does not divide $1$ lead us to the assumption that the finitely many primes must be wrong. I understand how we reached the contradiction. I don't understand why contradiction leads us to the conclusion shows that are assumption that there is only finitely many primes is wrong.


My apologies for the long post. Thanks for any and all help.

$\endgroup$
  • 2
    $\begingroup$ unique factorization requires a unique prime decomposition. If no $p$ exists, there must be a new prime... $\endgroup$ – Eleven-Eleven Oct 8 '16 at 23:50
  • 16
    $\begingroup$ The point of the argument is that there must be some prime not in the list that divides the number you produce. Your example confirms this! You found two such primes $59,509$ neither of which is on the list. Thus, your list can't have been complete. $\endgroup$ – lulu Oct 8 '16 at 23:51
  • 2
    $\begingroup$ The proof makes an assumption that there are finitely many primes, But it then goes on to show, given the conditions, this actually can't be the case. Therefore, the flaw is in your assumption, since all arguments in the proof are mathematically valid. $\endgroup$ – Eleven-Eleven Oct 8 '16 at 23:53
  • 1
    $\begingroup$ As stated above, all of your mathematical arguments are correct when you started from your original assumption. Yet you are led to a point in the proof that is impossible. If the mathematical arguments are sound and correct, what is left for there to be wrong...? The original assumption must therefore be incorrect. $\endgroup$ – Eleven-Eleven Oct 8 '16 at 23:55
  • 1
    $\begingroup$ 2) In this case that there are at least 7 primes. But if you generalize this, that p1p2...pn+1 is never divisible by p1,...,pn then p1,.....pn can not be a list of all primes. No such list can exist. So there can not be a finite number of primes. $\endgroup$ – fleablood Oct 9 '16 at 0:33
43
$\begingroup$

This is an excellent example of a proof that is traditionally phrased as a proof by contradiction but is much better understood constructively. From a constructive viewpoint, the proof shows that given any list of primes $p_1, \ldots, p_n$ there is a prime $q$ (any prime divisor of $p_1p_2\ldots p_n + 1$) that is distinct from each $p_i$. So given any finite set of primes we can find a prime that is not in that set.

$\endgroup$
  • 15
    $\begingroup$ +1 for emphasizing the constructive aspect of this proof. $\endgroup$ – P Vanchinathan Oct 9 '16 at 0:44
  • 2
    $\begingroup$ Except that this process doesn't actually construct a new prime (the example $y = 30031$ being composite). $\endgroup$ – Daniel R. Collins Oct 9 '16 at 2:20
  • 11
    $\begingroup$ @Rob: I think Daniel’s point is that the proof constructs an integer $y>1$ that is not divisible by $p_1$, $p_2$, …, $p_n$, and then it asserts that there must be a prime $q$ such that $q \mid y$, but it doesn’t construct $q$. $\endgroup$ – Scott Oct 9 '16 at 4:10
  • 2
    $\begingroup$ @Scott But there's a simple algorithm to generate a prime divisor of any given integer. $\endgroup$ – Jack M Oct 9 '16 at 8:05
  • 9
    $\begingroup$ @djechlin This is a constructive proof and you're utterly wrong. The set of divisors of a positive integer is finite. Now just take the minimal element greater than $1$ in the set of divisors; this is obviously prime. Would you say that finding the minimal element in a finite set of integers is not constructive? By the way, the proof by contradiction seems to imply that $p_1p_2\dots p_n+1$ is prime, which is the main source for confusion in newbies. $\endgroup$ – egreg Oct 9 '16 at 11:20
13
$\begingroup$
  1. The proof does break down in a sense. You have reached a contradiction, which means the hypothesis that there are finitely many primes can not possibly be true.

  2. So you thought you had 6 primes, you found 2 extra. Can you just add these two to your list and get all of the primes? If you repeat the process on these 8 primes, you will find that you will have even MORE primes by considering the product + 1. You can keep going and going and you will never run out of primes. This is the idea of the proof. It uses contradiction because you can do it all in one step and avoid the potential issue of doing the process infinitely many times.

$\endgroup$
8
$\begingroup$

Suppose only 6 primes exist: 2,3,5,7,11,13

However, none of the 6 primes listed, (2,3,5,7,11,13), divides 30,031.

Then we already have a contradiction. Since there are only 6 primes (we supposed that at the beginning) and none of them divide 30,031, then 30,031 must be prime. However, 30,031 is not one of the only 6 primes that exist. So 30,031 cannot be prime, yet it must be prime.

So the proof works. In fact, it works precisely the same regardless of what set of numbers we suppose are the only primes that exist. Thus no finite set of numbers can include all the primes that exist. Thus there are an infinite number of primes.

$\endgroup$
  • $\begingroup$ I think you mean "... no finite set of numbers ..." $\endgroup$ – origimbo Oct 10 '16 at 10:48
5
$\begingroup$

You ask in #1 if the proof breaks down. No. What breaks down is the assumption that there are no more primes. You assumed you had a complete list of primes. Then you constructed a number that is not divisible by any of the primes in your list. Only two possibilities remain: Either the number you constructed is prime, or it is divisible by a number that is not in your list. Either way your list is not complete, which contradicts your initial assumption.

Simpy put, you assumed you had a complete list and by using that assumption you proved that the list was not complete. The assumption must therefore be wrong.

The answer to #3 is basically the same. By finding a contradiction when you made an assumption, you proved the assumption to be incorrect.

The answer to #2 is no, you did not prove you anything by noting that 59 and 509 are both prime. You are trying to prove that there is a finite list of primes. If you choose a particular set of primes as you did {2, 3, 5, 7, 11, 13} and show that that particular set doesn't hold all the primes, a skeptic would just say that you need to add more primes (like 59 and 509) because you didn't make your set big enough. The proof has to be more general which is why it doesn't say how many primes are in the finite set. The proof is written so that it works no matter how big the finite set is.

$\endgroup$
4
$\begingroup$

Point 1: It's a theorem that any natural number $n>1$ has a prime factor. The proof is easy: for any number $n>1$, the smallest natural number $a>1$ which divides $n$ is prime (if it were not prime, it would not be the smallest).

Point 2: Yes, you have proved there are more than six primes. So what? The proof by contradiction doesn't suppose there are only six, but that there are a finite number of them.

Point 3: Actually, it's not really a proof by contradiction stricto sensu. It is proved that any finite list of primes in incomplete.

$\endgroup$
3
$\begingroup$

Here is a non-mathematical approach to the logic behind the proof by contradiction...

Suppose your assumption is that a suspect in a brutal murder is innocent because he said he couldn't have been at the location the person was murdered. You feel as though he is possibly telling the truth, but what you do know is that there are 5 other suspects. You know with 100% certainty due to the detail of the case there can't be anymore than 5 other suspects via proven information. But, the police can verify using obvious physical evidence such as video cameras that the 5 suspects could not possibly be guilty. Then there is either another suspect or the one assumed innocent is guilty. But we said that it was impossible for any other suspects to be considered. Therefore our original suspect is guilty.

This is exactly what is happening in a proof by contradiction.

$\endgroup$
  • 8
    $\begingroup$ This is good. But I think a better analogy is that you have 6 suspects and you assume that these are the only six possible suspects in the world. Then cameras show each and every one is innocent. Thus our assumption that we have all the suspects is wrong, and therefore there is a seventh possible person who could have (and did) do it. $\endgroup$ – fleablood Oct 9 '16 at 0:58
  • 1
    $\begingroup$ Damn.... you are right. It made logical sense when i wrote it... but yours is better. $\endgroup$ – Eleven-Eleven Oct 9 '16 at 1:02
  • 2
    $\begingroup$ Yours makes sense. And is a proof by contradiction. I just thought for this particular proof this is a closer analogy. I wouldn't say yours was wrong or anything. $\endgroup$ – fleablood Oct 9 '16 at 1:05
  • $\begingroup$ That was my original goal; understand why contradition works. But yours does that AND is analogous to the problem at hand. Thanks $\endgroup$ – Eleven-Eleven Oct 9 '16 at 1:07
  • 1
    $\begingroup$ I will concede. I get it. $\endgroup$ – Eleven-Eleven Oct 9 '16 at 23:01
2
$\begingroup$

The proof is essentially overexplaining. The point of contradiction would have been much clearer if the author had:

  1. Reached it earlier.
  2. Introduced less notation.

Since $p_1\cdots p_n+1$ cannot have any of $p_1,...,p_n$ as a prime factor we already have a contradiction.

The rest is just explaining to death why $p_1,...,p_n$ cannot be prime factors of $y=p_1\cdots p_n+1$ which should be clear since $y$ is $1$ off from being a multiple of either of those primes.

$\endgroup$
  • 5
    $\begingroup$ I think the gif dosn't really fit this site, though I can't say if there is a specific rule against such things $\endgroup$ – Yuriy S Oct 10 '16 at 11:27
  • 1
    $\begingroup$ @YuriyS: Hmm ... I am sorry to learn that people may find it inappropriate! That was by no means my intention! Do you think it would work better by removing the gif an leave the link and the figure of speach, or are all of those opfuscating the points I tried to make? $\endgroup$ – String Oct 10 '16 at 12:21
  • $\begingroup$ @String: your link to a cartoon movie of a dead animal being bludgeoned is disproportionate and offensive. $\endgroup$ – Rob Arthan Mar 12 '17 at 1:27
  • $\begingroup$ @RobArthan: Sorry, in some parts of the world such a cartoon would be considered merely a funny way to illustrate the saying about beating a dead horse. No offense intended, only a light tone. I cannot help that people do take offense, so I have removed it. Still it puzzles me how a cartoon matching the content of a saying would offend. I am from Denmark, after all. $\endgroup$ – String Mar 12 '17 at 8:11
  • $\begingroup$ @String: on MSE it's easier just to use neutral language. As I am English (after all), may I point out that the cliched phrase is actually "flogging a dead horse" and it doesn't have the connotations you think it does (it's not "explaining to death", it's using a tired old argument that has lost all interest or relevance). Your cartoon doesn't help with that. $\endgroup$ – Rob Arthan Mar 13 '17 at 1:55
1
$\begingroup$
  1. Well... yes... it does break down. You assumed that there are only 6 primes and reached a contradiction. You've successfully proved that there aren't only 6 primes.
  2. Under the assumption that there are only 6 primes 30,031 isn't factorizable.
  3. In proof by contradiction you prove proposition A by assuming A is not true, and through a series of logical steps reach an impossibility, thus proving that A must be true. Concurrently, in this proof, we assumed there is a finite number of primes. After a series of logical inferences we reached a contradiction. Since the only assumption we made in the process is that there are a finite number of primes, that assumption must be wrong.
$\endgroup$
1
$\begingroup$
  1. Either $ 6 $ primes you considered are not all the primes, or $ 30031 $ is a new prime. Either way assumption is false. Proof by contradiction.
  2. No, you haven't shown that two more primes exist. In this example yes, but not in general
  3. Again, based on your assumption you reached something impossible that $q $ divides $ 1$. There is no such $q $ except $1$.

Start with $ 2,3,5 $ being the only prime numbers. Then you would have $ 31 $ as the new number. $ 2,3,5 $ do not divide $ 31$. But unlike your case, $31$ is a prime number. So the assumption is wrong.

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