1. Banned
Join Date
Sep 2007
Posts
19
Cool. Really interesting game

2. Originally Posted by Homo Bibiens
DanishDynamite gave a correct answer, so probably he did everything correctly even though he did not explain. So I think it is his turn
Such trust!

All I can think of at the moment is the other proof from high school number theory that I remember. It is almost too banal to post, but I suppose it might be new for one or two readers, so here goes:

Prove that there are an infinite number of primes.

3. My unprofessional proof.
Suppose there is a number P(q) which is the biggest prime.
Then suppose M = P1 * P2 * .... P(q) Where P(n) is the nth prime.
M+1 would not factor any of the other primes because any division by a prime would result in remainder 1.
So M+1 would be the biggest prime.

Last edited by The_Radiation_Specialist; 2007-Sep-26 at 08:24 AM. Reason: making it more clear

My unprofessional proof.
Suppose there is a number P(q) which is the biggest prime.
Then suppose M = P1 * P2 * .... P(q) Where P(n) is the nth prime.
M+1 would not factor any of the other primes because any division by a prime would result in remainder 1.
So M+1 would be the biggest prime.

It is a contradiction, but there are two possibilities. Either M+1 is prime, or M+1 can be divided by some prime larger than P(n). In either situation, there is a prime larger than P(n).

5. Either M+1 is prime
,

In which case it would be the largest prime and larger than p(q) we assumed in the beginning. So there is a contradiction to the biggest prime. There cannot be a biggest prime.

or M+1 can be divided by some prime larger than P(n).
The primorials (product of all primes smaller or equal to a number) also included the largest prime we assumed in the beginning. So, no, M+1 cannon be divided without remainder by any prime based on our assumption in the beginning.

In either situation, there is a prime larger than P(n).

P(n) is not a prime by itself. It means simply the nth prime.
We assumed there p(q) is the biggest prime if primes were a finite number.

The primorials (product of all primes smaller or equal to a number) also included the largest prime we assumed in the beginning. So, no, M+1 cannon be divided without remainder by any prime based on our assumption in the beginning.
You are right, I did not apply the assumption that P(n) is the largest prime at this point. It is a different proof than the proof I know, but it is valid

7. What's the answer to life, the universe and everything?

8. Sorry, TRS, but I agree with Homo Bibiens. The proof I was looking for, and the one you attempted, was Euclid's proof (given in Euclid's own words here).

You cannot say "M+1 would be the biggest prime" because you don't know if it is a prime.

You can only say that either M+1 is a prime, because none of the primes in our list of primes can divide it, or there exists some other prime number not in our list which can divide it. But in either case, a prime number larger than p(q) exists, hence contradicting the premise.

What's the answer to life, the universe and everything?
42.

10. You cannot say "M+1 would be the biggest prime" because you don't know if it is a prime.
We assumed p(q) was to be the largest prime if there were finite primes. Then took M as the product of all primes from 2 to p(q). M+1 would not have any factors of all the primes we had in M. Therefore it would be a bigger prime.

So based on the assumption that there are finite primes (and there is a biggest prime) we arrive at a contradiction.

This is a bit different with Euclids proof as it assumes a biggest prime in the beginning.

We assumed p(q) was to be the largest prime if there were finite primes.
Yes, as does Euclid.
Then took M as the product of all primes from 2 to p(q). M+1 would not have any factors of all the primes we had in M. Therefore it would be a bigger prime.
But you don't know that it is a prime. It could very well be the product of 2 numbers larger than p(q). If so, it would not be a prime number.
So based on the assumption that there are finite primes (and there is a biggest prime) we arrive at a contradiction.

This is a bit different with Euclids proof as it assumes a biggest prime in the beginning.
Sorry, I don't see it.

12. But you don't know that it is a prime. It could very well be the product of 2 numbers larger than p(q). If so, it would not be a prime number.
Based on our assumption that p(q) is the biggest prime, M+1 must be a prime also.

I have to go to bed now. Will make more clarifications tomorrow if needed.

Based on our assumption that p(q) is the biggest prime, M+1 must be a prime also.
Yes, but as you say, that is based on your assumption. The point of this exercise is to show your assumption is wrong. In order to show that your assumption is wrong, you must then show that M+1 is in fact not a prime.

14. I've found another exercise (stolen from a math problem page I just found) which is the following:

Assume a cube. Assume that at one corner of the cube a fly sits, perfectly still. Assume that at the opposite corner of the cube (the corner furhest away from the fly corner) a blind spider is released. Assume that the spider can only move along the edges of the cube and does so randomly.

What is the expected number of edges that the spider will traverse before it hits upon the fly corner?

15. Originally Posted by DanishDynamite
I've found another exercise (stolen from a math problem page I just found) which is the following:

Assume a cube. Assume that at one corner of the cube a fly sits, perfectly still. Assume that at the opposite corner of the cube (the corner furhest away from the fly corner) a blind spider is released. Assume that the spider can only move along the edges of the cube and does so randomly.

What is the expected number of edges that the spider will traverse before it hits upon the fly corner?
Ten.

Every corner is 0, 1, 2, or 3 distance (measured by shortest path) from the fly corner. We can call x0 the expected number of edges to reach the fly corner from a distance of zero, x1 the expected number of edges to reach the fly corner from a distance of one, and so on.

x0=0 because the spider is already there.

From a distance of one, there is one path to the fly, and two paths to corners with a distance of two. So x1=1+(1/3)*x0+(2/3)*x2.

From a distance of two, there are two paths to corners with a distance of one, and one path to a corner with distance of three. So x2=1+(2/3)*x1+(1/3)*x3.

From a distance of three, all three paths lead to a distance of two, so x3=1+x2.

The equations are:

a) x0=0
b) x1=1+(1/3)*x0+(2/3)*x2
c) x2=1+(2/3)*x1+(1/3)*x3
d) x3=1+x2

Solution is:

x1=0
x1=7
x2=9
x3=10
Last edited by Sarawak; 2007-Sep-27 at 12:00 AM. Reason: To correct a mistake of explanation

16. Originally Posted by DanishDynamite
Yes, but as you say, that is based on your assumption. The point of this exercise is to show your assumption is wrong. In order to show that your assumption is wrong, you must then show that M+1 is in fact not a prime.
I think TRS has a correct proof by contradiction.

Assume p(n) is largest prime, and define M=p(1)*...*p(n).

Then M+1 is not divisible by p(1) through p(n) by construction. By assumption, there is no larger prime, so M+1 cannot be divisible by any number. But then, M+1 must be prime, so this is a contradiction. It is different from the proof you know (which is the same proof I know), but it is still valid.

17. Originally Posted by Homo Bibiens
Ten.

Every corner is 0, 1, 2, or 3 distance (measured by shortest path) from the fly corner. We can call x0 the expected number of edges to reach the fly corner from a distance of zero, x1 the expected number of edges to reach the fly corner from a distance of one, and so on.

x0=0 because the spider is already there.

From a distance of one, there is one path to the fly, and two paths to corners with a distance of two. So x1=1+(1/3)*x0+(2/3)*x2.

From a distance of two, there are two paths to corners with a distance of one, and one path to a corner with distance of three. So x2=1+(2/3)*x1+(1/3)*x3.

From a distance of three, all three paths lead to a distance of two, so x3=1+x2.

The equations are:

a) x0=0
b) x1=1+(1/3)*x0+(2/3)*x2
c) x2=1+(2/3)*x1+(1/3)*x3
d) x3=1+x2

Solution is:

x1=0
x1=7
x2=9
x3=10
Congrats!

18. Originally Posted by Homo Bibiens
I think TRS has a correct proof by contradiction.

Assume p(n) is largest prime, and define M=p(1)*...*p(n).

Then M+1 is not divisible by p(1) through p(n) by construction. By assumption, there is no larger prime, so M+1 cannot be divisible by any number. But then, M+1 must be prime, so this is a contradiction. It is different from the proof you know (which is the same proof I know), but it is still valid.
No, I'm afraid it isn't. See answer above.

19. Originally Posted by DanishDynamite
No, I'm afraid it isn't. See answer above.
I did see above, but the solution of TRS looks acceptable to me. I said before it had a problem because I read it carelessly, and only noted that it was different from the usual proof. But I think both are correct.

Proof by contradiction is to proof something is both true and false. If this is possible, then the axioms contain some inconsistency, and some axiom must be rejected. If we assume there is some largest prime and call it p(n), and define M as the product of all primes, then we have two statements:

A: There is some prime larger than p(n) but smaller than M+1 that divides M+1.
B: M+1 is prime.

The traditional proof shows that the statement (A or B) is false (by assumption that p(n) is largest prime), and that (A or B) is also true (by laws of arithmetic). So there is a contradiction.

The proof of TRS finds the contradiction in a different place. It shows that both A and B are false, by assumption that p(n) is largest prime. But by the laws of arithmetic, (A or B) is true. Since A is false, B is true. Therefore it proves that B is false and that B is true, so there is a contradiction.

20. Originally Posted by DanishDynamite
Congrats!

I will take a little time to try to think of a good question

21. Established Member
Join Date
Apr 2007
Posts
762
Originally Posted by Homo Bibiens
If we assume there is some largest prime and call it p(n), and define M as the product of all primes, then we have two statements:

A: There is some prime larger than p(n) but smaller than M+1 that divides M+1.
B: M+1 is prime.
Even though I'm quoting HB, I'm not saying HB is wrong, just making a quick point.

While it is true that proof by contradiction can be satisfied by showing either A or B must be true, in most cases, people leave out A. This is because you wish to show that if your assumptions are all correct, then you can derive a result contradictory to those assumptions. There is no need to further state that it's possible that your assumptions were incorrect to begin with, since that is what you are trying to show.

Thus, if you start out with a list p1, p2, p3... pq of primes for which pq>= all primes, there is no purpose in saying that M+1, where M is the product of all primes, might factor into some prime you left off the list. Your list must be comprehensive, and it can be since there are only finitely many primes if you assume there is a fixed largest prime.

After all, if you are allowed to have an incomplete list, you then also need to show what happens if M+1 factors into some prime pr such that pr<pq, that wasn't on the list. Then what will you do? If you say 'well, pr should've been in the product seeing as it's a prime,' then the same applies to the mysterious prime pw with M+1>pw>pq and M+1 factoring into pw. Why wasn't it on the list to begin with?

There's nothing wrong with including it, but it doesn't add anything to the proof, Euclid's version (admittedly, I haven't read it) notwithstanding.

22. . . .

23. Originally Posted by Homo Bibiens
I did see above, but the solution of TRS looks acceptable to me. I said before it had a problem because I read it carelessly, and only noted that it was different from the usual proof. But I think both are correct.

Proof by contradiction is to proof something is both true and false. If this is possible, then the axioms contain some inconsistency, and some axiom must be rejected. If we assume there is some largest prime and call it p(n), and define M as the product of all primes, then we have two statements:

A: There is some prime larger than p(n) but smaller than M+1 that divides M+1.
B: M+1 is prime.

The traditional proof shows that the statement (A or B) is false (by assumption that p(n) is largest prime), and that (A or B) is also true (by laws of arithmetic). So there is a contradiction.

The proof of TRS finds the contradiction in a different place. It shows that both A and B are false, by assumption that p(n) is largest prime. But by the laws of arithmetic, (A or B) is true. Since A is false, B is true. Therefore it proves that B is false and that B is true, so there is a contradiction.
TRS makes no mention of A at all in his proof. This is the problem. He simply states that M + 1 is not only a prime, but the biggest prime. The first part of that statement, that M + 1 is a prime, is simply not true and a wrong conclusion to draw. Once you have the product M + 1 and determine that this number cannot be divided (without remainder) by any of the known primes, the only conclusion one can draw at this point is that either A is true or B is true. Drawing the conclusion that B is true only, is simply wrong math.

An example of TRS's proof with a small introduction:

A prime number is a whole number which has no other factors than 1 and itself. Without giving the proof here, this means that any whole number is either a prime or a product of primes. Now on to TRS's proof....

Suppose the sixth prime p(6) = 13 is the biggest prime. Let M = p(1)*p(2)*...*p(6). Then the number M + 1 cannot be divided by any of the known primes and M + 1 is therefore a prime, and since it is bigger than p(6) it is also the largest prime. Since we assumed p(6) was the largest prime, we have a contradiction and p(6) cannot be the largest prime.

The part in bold is a wrong conclusion to draw as shown below:

M + 1 = p(1)*p(2)*p(3)*p(4)*p(5)*p(6) + 1
= 2*3*5*7*11*13 + 1
= 30031
= 59*509

Since the part in bold is wrong, everything that follows (in italics) is also wrong.

24. You could also argue that including that there is a prime pw, pk<pw<M+1 would contradict the first assumption which is saying that assume pk is the biggest prime.

The definition of a prime is as you stated:

A prime number is a whole number which has no other factors than 1 and itself.
So if it was a composite number (not a prime) it would be composed of a product of several primes. But in our assumption that p(k) was the biggest prime. No prime that was in our assumption (and we assumed these are all the primes that exist) would factor M+1. So based on our assumption and definition of a prime we could say M+1 would be another prime.

M + 1 = p(1)*p(2)*p(3)*p(4)*p(5)*p(6) + 1
= 2*3*5*7*11*13 + 1
= 30031
= 59*509
While true that primorial primes are not always a prime and can have factors that are larger than the largest prime factored, as you just showed, my example was based on an assumption that there weren't any primes bigger than p(k). When we establish that and make a primorial of p(k) then that + 1 would not factor all the primes we assumed there to exist. So it would be a new prime.

You could also argue that including that there is a prime pw, pk<pw<M+1 would contradict the first assumption which is saying that assume pk is the biggest prime.
Yes, I could argue that, and that is exactly what Euclid argued. But you cannot simply omit this step in a proof.
So if it was a composite number (not a prime) it would be composed of a product of several primes.
This is true, and the proof is simple, but it is a statement that needs to be proved.
But in our assumption that p(k) was the biggest prime. No prime that was in our assumption (and we assumed these are all the primes that exist) would factor M+1. So based on our assumption and definition of a prime we could say M+1 would be another prime.
Yes, we could say it would need to be a prime because although it doesn't need to be, the only alternative is that a number >p(q) divides M + 1 and this would also go against our assumption. BUT, the point is that we need to say this in our proof, otherwise the proof is not a proof.
While true that primorial primes are not always a prime and can have factors that are larger than the largest prime factored, as you just showed, my example was based on an assumption that there weren't any primes bigger than p(k). When we establish that and make a primorial of p(k) then that + 1 would not factor all the primes we assumed there to exist. So it would be a new prime.
Yes, but you need to say this. A proof is a step by step affair. Your proof is Euclid's proof, you just forgot to explicitly mention a step in the logical process.

No worries.

26. Originally Posted by DanishDynamite
Yes, but you need to say this. A proof is a step by step affair. Your proof is Euclid's proof, you just forgot to explicitly mention a step in the logical process.
I did mention rather "unprofessional proof"

Well speaking of infinite prime proving there is another one from Euler which is elegant.

First consider the sequence:
1+1/4+1/9+1/16+... = Infinite Sum (n=1) [1/n^2]

This is bigger than zero, obviously and converges (in another proof which I won't include here).

Now according to the fundamental theorem of arithmetic every number has a unique combination of product of primes. Which is elegantly included in:

(1 + 1/2 + 1/2^n + 1/2^2n + 2^3n +...) * (1 + 1/3 + 1/3^n + 1/3^2n +.....) * (1 + 1/5 ...)

This would produce the sum of all inverse square numbers for n=2, sum of all inverse numbers (does not converge) for n=1 and so on.

(1 + 1/2 + 1/2^n + 1/2^2n + 1/2^3n +...) can be written as 1/(1-(1/2^n))

as it is what it converges to in an infinite summation.

and generally it would be for any number (m) , 1/(1-(1/m^n))

And using the fundamental theorem of mathematics and this result we can have an infinite product of all the primes this way.

So it would be
Infinite Sum (n=1) [1/n^q] = Infinite product (n=1) [1/(1-(1/p^q))

where n is all integers and p is all primes. Therefore there has to be infinite primes as we know that the replacing q by 2 would converge and be greater than zero.

27. Established Member
Join Date
Apr 2007
Posts
762
Originally Posted by DanishDynamite

Yes, but you need to say this. A proof is a step by step affair. Your proof is Euclid's proof, you just forgot to explicitly mention a step in the logical process.
Depending on the phrasing of the assumptions in the original proof, this does not need to be said. The basic core of the proof is thus:
We hypothesize there are finitely many primes of which pq is the largest.
If M=the product of all primes, then M+1 is itself a prime. Since M+1>pq, we have a contradiction to disprove the hypothesis.

That's it. There is no need to say, maybe M+1 is composite and can factor into some prime pr that wasn't in the product somewhere. This is because of the word 'all' in the antecedent. Once you've made an assumption, you cannot challenge its validity later in the same proof.

Your own example (of factoring a short product of a few primes) does not have significance in this proof because you are showing the inverse of the statement. Specifically, you show:
If M=the product of some primes, then M+1 can be composite.

That does not mean anything since the original antecedent states that M must be the product of all primes, not some small finite set of primes.

To extend this to another example, in the proof that sqrt(2) is irrational, you must then also agree that my proof was incomplete. I must say, that either (a,b,)>1, which creates a contradiction, or that a/b was not sqrt(2) to begin with. This latter part would then need to be accounted for somehow, and I have never seen that in any proof.

28. Established Member
Join Date
Apr 2007
Posts
762
Originally Posted by mr obvious
Once you've made an assumption, you cannot challenge its validity later in the same proof.
Just to clarify, you cannot challenge its validity in the same proof by pulling an exception out of the air. A proof by contradiction has at its root a demonstration of inconsistency that challenges the assumption, but said challenge must be derived.

So if you say 'I have a finite set of all the primes,' I can say, 'you can't, because from whatever finite set you have, I can generate a new one that isn't in that set.' I cannot say 'Maybe there is one that you missed,' as a mathematical proof.

If you wish to think about this some more, why don't you assume that M+1 is composite (where M is the product of all primes). Now prove to me that some prime factor pw that divides M+1 must be greater than pq, which was the largest prime postulated in the hypothesis. Remember, you have relaxed the condition in the antecedent so that when I said 'all primes,' obviously there are some primes less than M+1 that haven't been included. Your job is to demonstrate why a prime factor of M+1 must be greater than pq, without introducing new terms into the proof (e.g., you can't assume consecutiveness or anything that wasn't already explicitly stated in your proof).

29. Originally Posted by mr obvious
Depending on the phrasing of the assumptions in the original proof, this does not need to be said. The basic core of the proof is thus:
We hypothesize there are finitely many primes of which pq is the largest.
If M=the product of all primes, then M+1 is itself a prime. Since M+1>pq, we have a contradiction to disprove the hypothesis.

That's it. There is no need to say, maybe M+1 is composite and can factor into some prime pr that wasn't in the product somewhere. This is because of the word 'all' in the antecedent. Once you've made an assumption, you cannot challenge its validity later in the same proof.

Your own example (of factoring a short product of a few primes) does not have significance in this proof because you are showing the inverse of the statement. Specifically, you show:
If M=the product of some primes, then M+1 can be composite.

That does not mean anything since the original antecedent states that M must be the product of all primes, not some small finite set of primes.

To extend this to another example, in the proof that sqrt(2) is irrational, you must then also agree that my proof was incomplete. I must say, that either (a,b,)>1, which creates a contradiction, or that a/b was not sqrt(2) to begin with. This latter part would then need to be accounted for somehow, and I have never seen that in any proof.
I have already explained where TRS went wrong. If you still feel his proof is valid and different from Euclid's proof, I suggest you send in your thoughts to the current Mathematical body in charge of these things. I'm sure they will be utterly amazed at this new revolutionary way of proving this simple concept.

30. Established Member
Join Date
Apr 2007
Posts
762
To DanishDynamite:

I am not saying Euclid's proof is incorrect. I am saying your claim that TRS's proof is incomplete is incorrect. I have looked at the Wiki page you linked to. There, Euclid simply states that the product of some finite number of primes plus one is either prime or must factor a prime that wasn't in the product. He made no claims that the finite set of primes was exhaustive. Since TRS claimed (or rather strongly implied) at the very beginning of his proof that he is enumerating all primes P1, P2, etc until Pq as the largest prime, he can skip the extra step.

So, yes, TRS's proof is complete and does not require any additional statements, even if it is not fluently stated. For example, see here:
http://mathforum.org/library/drmath/view/55855.html

He says there are two possibilities, that M+1 is prime, or that M+1 divides the existing, enumerated primes. Note that he does not include a random prime that divides M+1 and was not enumerated. Or see here:
http://www.jcu.edu/math/vignettes/primes.htm

You see, they also do not postulate the existence of some mysterious prime pw > pq. In all proofs that I see where the primes are listed exhaustively and there is a maximum designated, the only comment is that if M+1 is not prime, it must factor into an existing, enumerated prime, but it can't because there would be a remainder of one.

Again, here:
http://www.math.utah.edu/~pa/math/q2.html

You see in the upper box of the proof again, they do not list the condition where M+1 can factor into some mysterious unlisted prime.

In all of these cases, the argument is as I have outlined (although in most cases, the argument is flipped - but still equivalent). There is no need to postulate that there may be some Pw, where Pw wasn't on the list of the primes being multiplied, that divides M+1.

Since I have provided many sources and have explained why your understanding of the Wiki section is incorrect, I hope you'll take back your unnecessarily sarcastic and rude comments. I also note that you did not rise to the challenges posed by me in the preceding posts, which were not addressed in any of your previous explanations.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•