MangoJ Joined: Mar 12, 2011
• Threads: 10
• Posts: 905
December 17th, 2013 at 1:57:21 PM permalink
Quote: Greasyjohn

Where 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^^).
Greasyjohn Joined: Dec 8, 2013
• Threads: 133
• Posts: 2169
December 18th, 2013 at 9:48:28 AM permalink
Quote: MangoJ

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^^).

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.
dwheatley Joined: Nov 16, 2009
• Threads: 25
• Posts: 1246
December 18th, 2013 at 10:18:59 AM permalink
Quote: Greasyjohn

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 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?
Wisdom is the quality that keeps you out of situations where you would otherwise need it
AxiomOfChoice Joined: Sep 12, 2012
• Threads: 32
• Posts: 5761
December 18th, 2013 at 11:26:40 AM permalink
Quote: Greasyjohn

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 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.
Greasyjohn Joined: Dec 8, 2013
• Threads: 133
• Posts: 2169
December 18th, 2013 at 4:34:55 PM permalink
Thanks for trying to turn on the bulb in my vacant head but I still don't get it. And it's unfair 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.
Greasyjohn Joined: Dec 8, 2013
• Threads: 133
• Posts: 2169
December 18th, 2013 at 4:38:34 PM permalink
Quote: AxiomOfChoice

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.

Thanks, I'll read this over until I get it ( or pull my hair out).
beachbumbabs
Administrator Joined: May 21, 2013
• Threads: 99
• Posts: 14232
December 18th, 2013 at 10:55:53 PM permalink
Quote: Greasyjohn

Thanks 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.
If the House lost every hand, they wouldn't deal the game.
Greasyjohn Joined: Dec 8, 2013
• Threads: 133
• Posts: 2169
December 19th, 2013 at 3:05:58 AM permalink
Quote: beachbumbabs

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.

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?
Wizard
Administrator Joined: Oct 14, 2009
• Threads: 1375
• Posts: 22941
December 19th, 2013 at 3:34:43 AM permalink
Quote: Greasyjohn

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?

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.
It's not whether you win or lose; it's whether or not you had a good bet.
s2dbaker Joined: Jun 10, 2010
• Threads: 51
• Posts: 3259
December 19th, 2013 at 4:21:17 AM permalink
Perhaps it should be mentioned that a prime number is divisible, with no fractional part, by the number one and itself and no other integers..
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.
Someday, joor goin' to see the name of Googie Gomez in lights and joor goin' to say to joorself, "Was that her?" and then joor goin' to answer to joorself, "That was her!" But you know somethin' mister? I was always her yuss nobody knows it! - Googie Gomez

• Jump to: