Cool. Really interesting game
Cool. Really interesting game
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.
There is a contradiction.
Last edited by The_Radiation_Specialist; 2007-Sep-26 at 08:24 AM. Reason: making it more clear
,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.
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.or M+1 can be divided by some prime larger than P(n).
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.
What's the answer to life, the universe and everything?
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.
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.You cannot say "M+1 would be the biggest prime" because you don't know if it is a 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.
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.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.
Sorry, I don't see it.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.
Based on our assumption that p(q) is the biggest prime, M+1 must be a prime also.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.
I have to go to bed now. Will make more clarifications tomorrow if needed.
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?
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:
Last edited by Sarawak; 2007-Sep-27 at 12:00 AM. Reason: To correct a mistake of explanation
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.
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.
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.
. . .
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
Since the part in bold is wrong, everything that follows (in italics) is also wrong.
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:
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.A prime number is a whole number which has no other factors than 1 and itself.
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.M + 1 = p(1)*p(2)*p(3)*p(4)*p(5)*p(6) + 1
= 2*3*5*7*11*13 + 1
This is true, and the proof is simple, but it is a statement that needs to be proved.So if it was a composite number (not a prime) it would be composed of a product of several primes.
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.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, 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.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.
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.
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.
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).
Let us know about the feedback you receive.
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:
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:
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.
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.