Proof there's no highest prime number
Now lets define the number x = p1*p2*p3*p4*...*pL + 1.
What it means to be prime is that no other smaller prime divides into it evenly.
If we divide p1, p2, p3, ... pL into x we get a remainder of 1 every time.
You might argue that maybe a prime bigger than pL divides into x evenly. Yes, but then you would have found a larger prime than the so-called largest prime. If not, then x because a new largest prime, proving the initial conjecture of the existence of a largest prime by contradiction.
If one picks a number it has to be proven as prime to validate the theory.
So the search for primes that is "the largest prime" is also infinite.
Its best to say the question, "What is the largest prime number?" remains unresolved: not that it does not exist.
Since numbers are infinite,there is NO maximum or end to it. It is not unresolved, the largest prime number does not exist at all cause numbers are infinite.
First, some notation. We say "a divides b" if you can divide b by a and get no remainder. So, for example, 2 divides 6 but 2 does not divide 11.
Now, for some number p that is larger than 1, if p divides x, then p does not divide x + 1. For example, 3 divides 6 but 3 does not divide 7. The next number after 6 which is divisible by 3 is 6+3=9.
So, we are going to do a proof by contradiction. That is, we are going to assume that there are only finitely many primes, and then show that this leads to a contradiction, so our initial assumption must have been wrong.
Assume that there are only finitely many primes. Multiply them all together; you get a number. We will call that number x. All of the primes divide x. That means that none of the primes divide x+1. This is a contradiction (all numbers have a prime factorization). So our initial assumption (that there are only finitely many primes) must have been incorrect. Therefore, there are infinitely many primes.
That's it. If you still find this too advanced, maybe the problem is that it's difficult to jump right into something without first having the background. You have to walk before you can run, as the saying goes. Perhaps you should pick up an entry-level college textbook on Abstract Algebra or Classical Algebra (look for something with one of these two things in the title). It will take you through the introduction of really basic number theory, modular arithmetic, etc, and this will be a result that should be proven relatively early on. (Note that there are other ways to prove it, but this is by far the simplest way). This is actually a really interesting field of mathematics, so hopefully you will enjoy it.
Quote: GreasyjohnThanks everyone for your responses. I'm still in the dark. An example of the equation might help. 2x 3 x 5 x7 plus one is a prime, 211, but if you continue with the calculation and multiply 210 x 9 plus 1 you get 1,891 which is not a prime. If someone could write out the calculation that when added to 1 is always a prime, that would be great!
First: 9 is not prime. You probably wanted 11.
Second: there is no known solution to what you're asking for. You just have to calculate it, and check for primality. In general, finding large primes is computationally difficult! There is no easy way to generate them.
If you find this interesting, you might also want to look at Mersenne numbers, which are of the form 2^n - 1. http://en.wikipedia.org/wiki/Mersenne_prime
Note that this is unrelated to the proof that there are infinitely many primes.
Wizard's proof is valid. But it doesn't say that you can use the formula if pL is not the "largest" prime.
(or in other words, the formula makes sense only if you multiply ALL prime numbers together.)
Quote: GreasyjohnThanks everyone for your replies. I have the book One Two Three Infinity and just love this stuff. I had thought that what was being stated ( which I didn't grasp) was that if you multiply primes ie, 2x3x5x7x11x13 etc., that the answer you get after any multiplication (plus one) is a prime. But when you get to 2,310 x 13 plus one you get 30,031 which is not a prime. I thought, by what I was reading, that by mulitplying all the primes together you would always get a number that if added to one would be a higher prime. I guess there is no such formula.
Don't feel bad about it. I thought this too the first time I saw this proof (it was near the beginning of my math education). It takes a while to get used to mathematical rigor!
Guess what: it is conjectured that there are infinite twin primes. Currently the highest known twin primes are 2003663613 · 2^195000 ± 1.
This is an area where patterns and beauty are tantalizingly close, but the best pure mathematicians who ever lived have not been able to pin down formulas that describe their behavior.
Quote: GreasyjohnThanks everyone for your replies. I have the book One Two Three Infinity and just love this stuff. I had thought that what was being stated ( which I didn't grasp) was that if you multiply primes ie, 2x3x5x7x11x13 etc., that the answer you get after any multiplication (plus one) is a prime. But when you get to 2,310 x 13 plus one you get 30,031 which is not a prime. I thought, by what I was reading, that by mulitplying all the primes together you would always get a number that if added to one would be a higher prime. I guess there is no such formula.
30,031 is prime though.
Your thought was correct. Multiple all the primes below any number together, add one, you'll have a prime number. Just pick a number, find all the primes, and away you go.
This method doesn't calculate all the primes, though. Just shows that there is always a higher one.
EDIT : this post is incorrect.
Quote: thecesspitYour thought was correct. Multiple all the primes below any number together, add one, you'll have a prime number.
That's not correct.
Quote: AxiomOfChoiceIn fact, what do you think 59 * 509 is?
Derp... Apologies. 30,031... I totally misunderstood the point of the proof, and will now go shut the hell up :D
Quote: thecesspitDerp... Apologies. 30,031... I totally misunderstood the point of the proof, and will now go shut the hell up :D
Heh, no problem. As I said, I made the exact same mistake the first time I heard the proof. It's kind of subtle!
The key is that, even though the product + 1 can't be divided by any primes in your original list, there might be primes higher than the numbers in the list but still lower than the product + 1. So it could be divisible by "medium-sized" primes only. (This still violates the assumption that the list is complete, of course, so the proof still holds)
9 is not prime.Quote: GreasyjohnThanks everyone for your responses. I'm still in the dark. An example of the equation might help. 2x 3 x 5 x7 plus one is a prime, 211, but if you continue with the calculation and multiply 210 x 9 plus 1 you get 1,891 which is not a prime. If someone could write out the calculation that when added to 1 is always a prime, that would be great!
I used to do Mersenne Primes but my CPU kept heating up and crashing the calc. I would only be successful about 80% of the time with each iteration taking a month. It sucks to lose nearly a month's worth a work because your CPU fan is too small or not perfectly seated. Now I play Bejeweled Blitz and my CPU is much happier.Quote: AxiomOfChoiceIn general, finding large primes is computationally difficult! There is no easy way to generate them.
Quote: GreasyjohnWhere you say "let's define the number x..." what is that in plain English?
It's the same as "think about the number you would get from multiplying p1 by p2 and p3 and ... and pL, and add 1. For short, let's call this resulting number x".
The "math" you use is: even if you don't know any exact value of pL or x or anything else, you still know some properties - and you can play with those properties.
One property of pL: it is the largest prime number (because you assumed there is one such largest prime number, which you called pL).
One property of x: it is a prime number (as no other prime number divides evenly by it, it must be a prime number by itself).
Another property of x: x is larger than pL.
These three properties do not fit together. If x is a prime number and is larger than pL, then pL cannot be the largest prime number (because you found a prime number "x" which is larger than pL). If all three properties contradict each other, at least one of them must in fact be false. The last property ("x is larger than pL") seems true as all prime numbers are larger than 1. The second property "x is a prime number" is also true, as can be calculated from the definition of x.
So the only thing that must be false is the first property "pL is the largest prime number". If there is no such pL which could be declared "largest prime number" the only valid conclusion is that there in fact no largest prime number (or logic doesn't work at all^^).
Quote: MangoJIt's the same as "think about the number you would get from multiplying p1 by p2 and p3 and ... and pL, and add 1. For short, let's call this resulting number x".
The "math" you use is: even if you don't know any exact value of pL or x or anything else, you still know some properties - and you can play with those properties.
One property of pL: it is the largest prime number (because you assumed there is one such largest prime number, which you called pL).
One property of x: it is a prime number (as no other prime number divides evenly by it, it must be a prime number by itself).
Another property of x: x is larger than pL.
These three properties do not fit together. If x is a prime number and is larger than pL, then pL cannot be the largest prime number (because you found a prime number "x" which is larger than pL). If all three properties contradict each other, at least one of them must in fact be false. The last property ("x is larger than pL") seems true as all prime numbers are larger than 1. The second property "x is a prime number" is also true, as can be calculated from the definition of x.
So the only thing that must be false is the first property "pL is the largest prime number". If there is no such pL which could be declared "largest prime number" the only valid conclusion is that there in fact no largest prime number (or logic doesn't work at all^^).
Thank you for your reply. But, for instance, if we assume that 13 is the largest prime number then the equation plus one = 30,0031 which is not a prime. And if this example demonstrates that the equation doesn't always work then we can't PROVE that it works at all for very large numbers ( since all primes ARE known up to numbers containing some 17,000,000 digits). I'm not saying I'm right, in fact I'm sure I'm wrong, but this is how it appears to me.
Quote: GreasyjohnThank you for your reply. But, for instance, if we assume that 13 is the largest prime number then the equation plus one = 30,0031 which is not a prime. And if this example demonstrates that the equation doesn't always work then we can't PROVE that it works at all for very large numbers ( since all primes ARE known up to numbers containing some 75,000,000 digits). I'm not saying I'm right, in fact I'm sure I'm wrong, but this is how it appears to me.
If we assume that 13 is the largest prime, you get 30,031. We know this is 59*509. We know 59 is prime. Which violates our assumption that 13 was the largest prime!
So let's multiple all the primes up to 59...
See where I'm going with this?
Quote: GreasyjohnThank you for your reply. But, for instance, if we assume that 13 is the largest prime number then the equation plus one = 30,0031 which is not a prime. And if this example demonstrates that the equation doesn't always work then we can't PROVE that it works at all for very large numbers ( since all primes ARE known up to numbers containing some 75,000,000 digits). I'm not saying I'm right, in fact I'm sure I'm wrong, but this is how it appears to me.
30.031 is not prime, but is it also not divisible by any prime 13 or less. Which proves that 13 was not the highest prime.
So, suppose there are only finitely many primes. Call the biggest one "p". Multiply all the prime numbers less than or equal to p. Add 1. Your new number is not divisible by and prime less than or equal to p. So, p is not the largest prime. This contradicts our original assumption.
The goal here is not to find new primes. The goal here is to prove that there is no largest one. We don't prove it by finding a bigger one, we prove it by showing that if you assume that there is a largest one, you arrive at a contradiction (ie, your assumption is false).
Another way of looking at this is, we don't directly prove that there are infinitely many primes. Instead, we do it indirectly, by proving that the statement "there are finitely many primes" is false.
Quote: AxiomOfChoice30.031 is not prime, but is it also not divisible by any prime 13 or less. Which proves that 13 was not the highest prime.
So, suppose there are only finitely many primes. Call the biggest one "p". Multiply all the prime numbers less than or equal to p. Add 1. Your new number is not divisible by and prime less than or equal to p. So, p is not the largest prime. This contradicts our original assumption.
The goal here is not to find new primes. The goal here is to prove that there is no largest one. We don't prove it by finding a bigger one, we prove it by showing that if you assume that there is a largest one, you arrive at a contradiction (ie, your assumption is false).
Another way of looking at this is, we don't directly prove that there are infinitely many primes. Instead, we do it indirectly, by proving that the statement "there are finitely many primes" is false.
Thanks, I'll read this over until I get it ( or pull my hair out).
Quote: GreasyjohnThanks for trying to turn on the bulb in my vacant head but I still don't get it. And it's unfar of me to take up your time with this when I barely passed agebra and don't remember much about it anyway. So no, I don't see where you're going with this. But I will read some of the ealier posts to see if I can crawl a few steps forward.
If I am understanding this correctly: The hard part is trying to prove a negative. It's indirect, because using 30,031 proof (multiplying all primes up to and including 13, and adding 1), you're just trying to show (hypothesize) that 13 is the highest prime number. You do the calculation. You get a number that is divisable by a number that's NOT one of those primes you used to get it, which is 59. So 30,031 is not itself a prime number.
HOWEVER, you found a number (59) that IS higher than 13, AND is only divisible by itself and 1. ERGO, there IS a number higher than 13 that is a prime. So, 13 is not the HIGHEST prime number, and that proof is false.
You just keep doing this for any sequence of primes, and you can continue to prove there is ALWAYS a higher prime (like finding 59) than the one you said was the highest in order to do the calculation. So what you've really proved is that there is no absolute highest prime number (by extrapolation of the information; they're saying this ALWAYS works, no matter how high you go).
Sorry for the redundancy in phrasing; I'm saying the same thing several ways hoping to make the thing that itches in your head click; I think you were almost there.
Quote: beachbumbabsIf I am understanding this correctly: The hard part is trying to prove a negative. It's indirect, because using 30,031 proof (multiplying all primes up to and including 13, and adding 1), you're just trying to show (hypothesize) that 13 is the highest prime number. You do the calculation. You get a number that is divisable by a number that's NOT one of those primes you used to get it, which is 59. So 30,031 is not itself a prime number.
HOWEVER, you found a number (59) that IS higher than 13, AND is only divisible by itself and 1. ERGO, there IS a number higher than 13 that is a prime. So, 13 is not the HIGHEST prime number, and that proof is false.
You just keep doing this for any sequence of primes, and you can continue to prove there is ALWAYS a higher prime (like finding 59) than the one you said was the highest in order to do the calculation. So what you've really proved is that there is no absolute highest prime number (by extrapolation of the information; they're saying this ALWAYS works, no matter how high you go).
Sorry for the redundancy in phrasing; I'm saying the same thing several ways hoping to make the thing that itches in your head click; I think you were almost there.
I feel like the ape in the opening scenes of the movie 2001. I'm holding the femur bone but I haven't figured out that it's a tool. Thanks for your very clear articulation, it allows me to state clearly what I don't get: We know, let's assume, that 13 is the highest prime, we do the math, and come to 30,031. Yes, we can show that 30,031 is not a prime because it is a factor of 59 and 509. But in order to show that 30,031 is a factor of 59 and 509 we'd have to stumble upon the equation. Just arriving at the number 30,031 doesn't guide us to 59 or 509. 2,310 x 13 and arriving at 30,031 doesn't identify 59 or 509. Where's the proof that there's a higher prime than 13 by arriving at 30,031?
Quote: GreasyjohnJust arriving at the number 30,031 doesn't guide us to 59 or 509. 2,310 x 13 and arriving at 30,031 doesn't identify 59 or 509. Where's the proof that there's a higher prime than 13 by arriving at 30,031?
We don't need to find 59 or 509 to know the proof works. We know logically that 2, 3, 5, 7, 11, and 13 don't divide 30,031 because we tacked on that one remainder to it. So, there are two possibilities with that number:
(1) A prime greater than 11 and less than 30,031 divides 30,031. Actually, we need to check as high as sqrt(30,031)=173, but let's not muddy the waters.
(2) No other prime divides it.
If (1) is true, then there is a prime greater than 13, which disproves the initial conjecture.
If (2) is true, then there is a prime greater than 13, which disproves the initial conjecture.
For those who don't understand the logic of this, it is called proof by contradiction. For any largest prime you claim to find, I can prove there is a larger prime. Because the "largest prime" conjecture can be contradicted for any value, it must not be true, proving the opposite that there is no largest prime.
Much like if you said "there is a largest number" I could add one to any number you produce and disprove your conjecture. Please don't mention infinity, lest we have to have 40 pages of posts arguing about what infinity is again.
Therefore:
To find out if a number is prime, you simply divide it by all of the numbers that are smaller than that number.
You only need to divide by all of the prime numbers because if a number is divisible by 6, then it's also divisible by 3.
You only need to divide by all of the prime numbers up to the square root of the number you are testing because:
X is the number you are testing, Pn is the prime number you are using to divide, Y is the result of the test so
X / Pn = Y
Let us say we are testing 211 to see if its prime
The Square Root of 211 is 14.5258
Since we only care about dividing by prime numbers,
211 / 2 = 105.50
211 / 3 = 70.33
211 / 5 = 42.2
211 / 7 = 30.14
211 / 11 = 19.18
211 / 13 = 16.23
Look what happens when you get to 17
211 / 17 = 12.41
This is the tricky part. The 12.41 number is less than 17 so that number will only get smaller as you increase the prime numbers that you divide by. So you don't need to go any further to determine if a number is prime or not. Notice the trend:
2 * 105.50 = 211
3 * 70.33 = 211
5 * 42.2 = 211
7 * 31.14 = 211
11 * 19.18 = 211
13 * 16.23 = 211
17 * 12.41 = 211
I've already checked all primes 13 and below so I need go no further.
211 is prime.
That's the basics.
Quote: WizardWe don't need to find 59 or 509 to know the proof works. We know logically that 2, 3, 5, 7, 11, and 13 don't divide 30,031 because we tacked on that one remainder to it. So, there are two possibilities with that number:
(1) A prime greater than 11 and less than 30,031 divides 30,031. Actually, we need to check as high as sqrt(30,031)=173, but let's not muddy the waters.
(2) No other prime divides it.
If (1) is true, then there is a prime greater than 13, which disproves the initial conjecture.
If (2) is true, then there is a prime greater than 13, which disproves the initial conjecture.
For those who don't understand the logic of this, it is called proof by contradiction. For any largest prime you claim to find, I can prove there is a larger prime. Because the "largest prime" conjecture can be contradicted for any value, it must not be true, proving the opposite that there is no largest prime.
Much like if you said "there is a largest number" I could add one to any number you produce and disprove your conjecture. Please don't mention infinity, lest we have to have 40 pages of posts arguing about what infinity is again.
If (1) is true how would you know it until you stumble upon the answer? Until you find the prime how can you prove it exists? If (2) is true, that no other prime divides it, same question, how would know without going through the myriad calculations?
If you know all the prime numbers up to X, then for all numbers less than or equal to X^2, you can determine if it is prime.Quote: GreasyjohnIf (1) is true how would you know it until you stumble upon the answer? Until you find the prime how can you prove it exists? If (2) is true, that no other prime divides it, same question, how would know without going through the myriad calculations?
Quote: WizardWe don't need to find 59 or 509 to know the proof works. We know logically that 2, 3, 5, 7, 11, and 13 don't divide 30,031 because we tacked on that one remainder to it. So, there are two possibilities with that number:
(1) A prime greater than 11 and less than 30,031 divides 30,031. Actually, we need to check as high as sqrt(30,031)=173, but let's not muddy the waters.
(2) No other prime divides it.
If (1) is true, then there is a prime greater than 13, which disproves the initial conjecture.
If (2) is true, then there is a prime greater than 13, which disproves the initial conjecture.
For those who don't understand the logic of this, it is called proof by contradiction. For any largest prime you claim to find, I can prove there is a larger prime. Because the "largest prime" conjecture can be contradicted for any value, it must not be true, proving the opposite that there is no largest prime.
Much like if you said "there is a largest number" I could add one to any number you produce and disprove your conjecture. Please don't mention infinity, lest we have to have 40 pages of posts arguing about what infinity is again.
Hello Wizard,
I just reread your first (and the first) reply to my original post and I think I may get it. 30,031 is either a prime (if no larger prime than the largest known prime--we were assuming 13--divides into it) or, 30,031 is not a prime because a prime greater than the largest known prime (13 again) divides into it, therefore there exists a prime greater than 13. We don't need to know whether 30,031 is prime or whether a prime divides into it, but we know it's one or the other. I know in writing this out I'm just restating what's already been stated but it's helping me to understand it by putting into my own words. Is this correct?
Quote: GreasyjohnWe don't need to know whether 30,031 is prime or whether a prime divides into it, but we know it's one or the other. I know in writing this out I'm just restating what's already been stated but it's helping me to understand it by putting into my own words. Is this correct?
Yes! We don't need to do any testing of it. We know either condition must be true, therefor we found a larger prime than the "largest prime."
If 30,031 is a prime, then you've found a prime number larger than 13.
If 30,031 is not a prime, then you've found a prime number larger than 13 (that being the number that divides evenly into 30,031)
Quote: stargazer... If 30,031 is not a prime, then you've found a prime number larger than 13 (that being the number that divides evenly into 30,031)
My nerdy wording would not be "you've found a prime number larger than 13" but rather "you've found that there must exist a prime number larger than 13."
Quote: WizardYes! We don't need to do any testing of it. We know either condition must be true, therefor we found a larger prime than the "largest prime."
I awoke this morning and looked to find that the first word of the day I was going to read was "Yes!". But then, as I was thinking about this proof we've been discussing, the question I now have and should have had before I wrote you my last message is this: 30,031 must be a prime or be be a multiple of a prime. I don't know how often p1*p2*p3 (etc.) +1 = a prime or doesn't = a prime. (I haven't read about it much but plan to.) Since 30,031 is NOT a prime why does it have to be a multiple of a prime larger than (in this example the largest known prime ) 13? If the p1*p2*... +1 equation can sometimes NOT be a prime why must the answer HAVE to be a multiple of a higher unknown prime? Why can't you get an answer that is not a prime and is not a multiple of a prime? Am I back to square one or can you extend me a branch lest I perish in the quicksand of ignorance?
Quote: GreasyjohnWhere's the proof that there's a higher prime than 13 by arriving at 30,031?
Because we know that 30,031 is NOT divisible by all the primes less than or equal to 13(**). Therefore, either 30,031 is prime, or it's divisible by some prime larger than 13. Either way, there is a prime larger than 13.
(**) we know this because 30,030 is divisible by all the primes less than or equal to 13, and so 30,031 can't be divisible by any of them. Because, remember, if 30,030 is divisible by p, the next number that is divisible by p is 30,030 + p (which is bigger than 30,031).
Quote: GreasyjohnWhy can't you get an answer that is not a prime and is not a multiple of a prime? Am I back to square one or can you extend me a branch lest I perish in the quicksand of ignorance?
This is based on something called the fundamental theorem of arithmetic, basically every number can be written as the product of primes spefically in a unique way though that part doesn't matter, so you can write the number you get as some product of primes. You also know that none of the numbers in your original list can divide the new number since you're always left with a remainder of 1. That means one of your prime factors has to be a prime that wasn't in the original list, but the original list was supposed to contain all the primes so you get a contradiction.
Quote: TwirdmanThis is based on something called the fundamental theorem of arithmetic, basically every number can be written as the product of primes spefically in a unique way though that part doesn't matter, so you can write the number you get as some product of primes. You also know that none of the numbers in your original list can divide the new number since you're always left with a remainder of 1. That means one of your prime factors has to be a prime that wasn't in the original list, but the original list was supposed to contain all the primes so you get a contradiction.
Okay, I'm thinking about this while I'm writing, and if it doesn't make sense to me when I'm done I won't post it: If the equation that led to 30,031 holds that 13 is the largest known prime since none of the primes 2,3,5,7,11,13 can divide into 30,031 then either 30,031 is a prime or some prime greater than the largest known prime (13) must exist. We've already proved that 30,031 is not divisible by 2,3,5,7,11,13 so 30,031 MAY be a prime.
(I'm looking at this again and rereading the Wizard's original post.)
So simply put, 30,031 is a prime or it's not. But all the evidence (known primes up to 13) suggest that it may be. If we start dividing all the odd numbers greater than 13 ( I know, this is overkill) into 30,031 we will either find a new larger prime than 13 or we won't. If we don't then 30,031 IS the new largest known prime. If we do, then there's a larger prime that is less than 30,031 but larger than 13. Either way there HAS TO ALWAYS BE A LARGER PRIME in the p1* p2* p3*...+1 equation. (Of course 59 and 509 divide into 30,031 so at the end of this equation ( where 13 was the largest known prime) we now have a NEW largest prime, 509.)
Even more simply: If no prime goes into 30,031 then 30,031 is a prime. If a larger prime than 13 goes into 30,031 then we have a NEW larger prime than 13. When I asked in the quote above, "Why can't you get an answer that is not a prime and is not a multiple of a prime?" which is the same thing as asking, "Why can't 30,031 not be a prime and have no prime that goes into it", these questions are not logical because if no prime goes into it IT must be a prime.
Remember that the goal of the proof is not to directly find a larger prime. It's just to show that one must exist, even though we don't know what it is.
With the example, we showed that there must be a larger prime than 13, but we did not explicitly find it. This is fine though -- it's all that's required to show that there are infinitely many primes. No matter which prime you choose, we can use this proof to show that there is a bigger one.
Quote: GreasyjohnHello Wizard,
I just reread your first (and the first) reply to my original post and I think I may get it. 30,031 is either a prime (if no larger prime than the largest known prime--we were assuming 13--divides into it) or, 30,031 is not a prime because a prime greater than the largest known prime (13 again) divides into it, therefore there exists a prime greater than 13. We don't need to know whether 30,031 is prime or whether a prime divides into it, but we know it's one or the other. I know in writing this out I'm just restating what's already been stated but it's helping me to understand it by putting into my own words. Is this correct?
Yay, Greasyjohn!!
Quote: GreasyjohnI awoke this morning and looked to find that the first word of the day I was going to read was "Yes!". But then, as I was thinking about this proof we've been discussing, the question I now have and should have had before I wrote you my last message is this: 30,031 must be a prime or be be a multiple of a prime. I don't know how often p1*p2*p3 (etc.) +1 = a prime or doesn't = a prime. (I haven't read about it much but plan to.) Since 30,031 is NOT a prime why does it have to be a multiple of a prime larger than (in this example the largest known prime ) 13? If the p1*p2*... +1 equation can sometimes NOT be a prime why must the answer HAVE to be a multiple of a higher unknown prime? Why can't you get an answer that is not a prime and is not a multiple of a prime? Am I back to square one or can you extend me a branch lest I perish in the quicksand of ignorance?
All divisable numbers (NOT-prime's) can be broken down into primes. All even numbers are divisable by 2, for the easiest example. There is no third state: either a number is prime, or it can be broken down into primes. (We're talking integers here, not fractions.) You're there, GJ, you got it. You're not back at square one. This is just how they prove what they already know in a universally accepted manner.
Quote: GreasyjohnI awoke this morning and looked to find that the first word of the day I was going to read was "Yes!". But then, as I was thinking about this proof we've been discussing, the question I now have and should have had before I wrote you my last message is this: 30,031 must be a prime or be be a multiple of a prime. I don't know how often p1*p2*p3 (etc.) +1 = a prime or doesn't = a prime. (I haven't read about it much but plan to.) Since 30,031 is NOT a prime why does it have to be a multiple of a prime larger than (in this example the largest known prime ) 13? If the p1*p2*... +1 equation can sometimes NOT be a prime why must the answer HAVE to be a multiple of a higher unknown prime? Why can't you get an answer that is not a prime and is not a multiple of a prime? Am I back to square one or can you extend me a branch lest I perish in the quicksand of ignorance?
No need to reply Wizard, I finally get it. Thanks for your and everyone's help.
It's been a couple of days and I've got a question. How does the equation continue? The beginning is easy since you have to use all the known primes and get to 30,031 before you have a number that is not a prime. So is the equation: 1x2x3x5x7x11x13x509+1? If now we're asking not "Is there a larger prime? but "What is the next largest prime?" is this how the calculation would continue? Or is 30,031 omitted from the calculation somehow since it is not a prime? Does it continue ...5x7x11x509+1 and avoid 13 in the calculation ( which gives us 1,175,791 which is a prime)?
If I'm going to explain this to my girlfriend as foreplay I need to know what I'm talking about!
Quote: GreasyjohnIt's been a couple of days and I've got a question. How does the equation continue? The beginning is easy since you have to use all the known primes and get to 30,031 before you have a number that is not a prime? So is the equation: 1x2x3x5x7x11x13x509+1? If now we're asking not "Is there a larger prime? but "What is the next largest prime?" is this how would the calculation would continue? Or is 30,031 omitted from the calculation somehow since it is not a prime? Does it continue ...5x7x11x509+1 and avoid 13 in the calculation ( which gives us 1,175,791 Which is a prime)?
If I'm going to explain this to my girlfriend as foreplay I need to know what I'm talking about!
Remember the proof isn't to find any prime it is just to show one exist. So multiply a random group of primes together and adding one doesn't guarantee you'll get a larger prime just not a prime in your list. So for instance 3x5+1=16 which is 2^4 so you didn't find a larger prime you just found a prime not on your list namely 2. So yeah the contradiction comes from us saying p1, p2, ..., pN was a list of all the primes. Since there were only a finite number of them we can list them all. We then find a prime not in our list. We can't say anything about the size of the prime we will get from this all we can say is its not in our initial list and that is a contradiction to our list containing all the primes.
Quote: GreasyjohnI completely understand that there's no largest prime. I was merely trying to continue the calculation. Perhaps there is no calculation--multiply any know primes and add one and there' s always a prime greater than ANY prime on our list.
Yes if you take a list of all the primes up to a certain value say 23 so you have 2*3*5*7*11*13*17*19*23+1 you will get a larger prime. Though you have to still find what that larger prime is by doing repeated divisions of the number and there are simply much easier ways to find incredibly large primes.
