Greasyjohn
Greasyjohn
Joined: Dec 8, 2013
  • Threads: 133
  • Posts: 2169
December 19th, 2013 at 4:33:32 AM permalink
Quote: Wizard

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.



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?
s2dbaker
s2dbaker
Joined: Jun 10, 2010
  • Threads: 51
  • Posts: 3259
December 19th, 2013 at 5:39:26 AM permalink
Quote: Greasyjohn

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.
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
Greasyjohn
Greasyjohn
Joined: Dec 8, 2013
  • Threads: 133
  • Posts: 2169
December 19th, 2013 at 6:15:07 AM permalink
Quote: Wizard

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.



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

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?



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."
It's not whether you win or lose; it's whether or not you had a good bet.
stargazer
stargazer
Joined: Jan 23, 2013
  • Threads: 1
  • Posts: 14
December 19th, 2013 at 7:58:15 AM permalink
Either way, you have proven that 13 is not the largest prime number.

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)
Doc
Doc
Joined: Feb 27, 2010
  • Threads: 45
  • Posts: 7076
December 19th, 2013 at 8:33:54 AM permalink
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."
Greasyjohn
Greasyjohn
Joined: Dec 8, 2013
  • Threads: 133
  • Posts: 2169
December 19th, 2013 at 10:33:04 AM permalink
Quote: Wizard

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."



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?
dwheatley
dwheatley
Joined: Nov 16, 2009
  • Threads: 25
  • Posts: 1246
December 19th, 2013 at 11:10:12 AM permalink
Because p1 through pn aren't it's divisors (they all leave a remainder of 1). So what else could divide it?
Wisdom is the quality that keeps you out of situations where you would otherwise need it
AxiomOfChoice
AxiomOfChoice
Joined: Sep 12, 2012
  • Threads: 32
  • Posts: 5761
December 19th, 2013 at 11:15:53 AM permalink
Quote: Greasyjohn

Where'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).
Twirdman
Twirdman
Joined: Jun 5, 2013
  • Threads: 0
  • Posts: 1004
December 19th, 2013 at 11:45:40 AM permalink
Quote: Greasyjohn

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?



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.

  • Jump to: