Greasyjohn
Greasyjohn
Joined: Dec 8, 2013
  • Threads: 134
  • Posts: 2172
December 19th, 2013 at 1:00:33 PM permalink
Quote: Twirdman

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.



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.
AxiomOfChoice
AxiomOfChoice
Joined: Sep 12, 2012
  • Threads: 32
  • Posts: 5761
December 19th, 2013 at 1:10:49 PM permalink
So, do you understand the proof now? It seems like you do?

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.
beachbumbabs
Administrator
beachbumbabs
Joined: May 21, 2013
  • Threads: 99
  • Posts: 14232
December 19th, 2013 at 1:55:02 PM permalink
Quote: Greasyjohn

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?



Yay, Greasyjohn!!
If the House lost every hand, they wouldn't deal the game.
beachbumbabs
Administrator
beachbumbabs
Joined: May 21, 2013
  • Threads: 99
  • Posts: 14232
December 19th, 2013 at 2:00:19 PM permalink
Quote: Greasyjohn

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?



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.
If the House lost every hand, they wouldn't deal the game.
Greasyjohn
Greasyjohn
Joined: Dec 8, 2013
  • Threads: 134
  • Posts: 2172
December 19th, 2013 at 2:41:01 PM permalink
I do now understand. Thanks to you and everyone else's help along the way!
Greasyjohn
Greasyjohn
Joined: Dec 8, 2013
  • Threads: 134
  • Posts: 2172
December 19th, 2013 at 3:41:09 PM permalink
Quote: Greasyjohn

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?



No need to reply Wizard, I finally get it. Thanks for your and everyone's help.
Greasyjohn
Greasyjohn
Joined: Dec 8, 2013
  • Threads: 134
  • Posts: 2172
December 21st, 2013 at 12:35:23 PM permalink
(I'm editing this to let you know that the following might be poppycock if my later post is correct.)

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!
Twirdman
Twirdman
Joined: Jun 5, 2013
  • Threads: 0
  • Posts: 1004
December 21st, 2013 at 12:43:22 PM permalink
Quote: Greasyjohn

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 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.
Greasyjohn
Greasyjohn
Joined: Dec 8, 2013
  • Threads: 134
  • Posts: 2172
December 21st, 2013 at 12:53:47 PM permalink
I 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.
Twirdman
Twirdman
Joined: Jun 5, 2013
  • Threads: 0
  • Posts: 1004
December 21st, 2013 at 1:01:08 PM permalink
Quote: Greasyjohn

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

  • Jump to: