Greasyjohn Joined: Dec 8, 2013
• Posts: 2172
December 16th, 2013 at 2:07:38 AM permalink
I have read the proof that there is no highest prime number, but having little knowledge of algebraic notation I am at a loss. The proof has something to do with multiplying primes like, say, 3,5,7 and then adding one. Does anyone have an easy to understand explanation?
Wizard Joined: Oct 14, 2009
• Posts: 23298
December 16th, 2013 at 4:32:34 AM permalink
Let's assume, for a minute, there is a largest prime. We can number the primes p1=2, p2=3, p3=5, p4=7, ... pL = largest prime.

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.
It's not whether you win or lose; it's whether or not you had a good bet.
Jeepster Joined: Jul 7, 2013
• Posts: 84
December 16th, 2013 at 7:26:20 AM permalink
Edited, as I misread the original post.
A photon without any luggage checks into a hotel, he's travelling light.
Greasyjohn Joined: Dec 8, 2013
• Posts: 2172
December 16th, 2013 at 8:55:40 AM permalink
Thanks for your reply, Wizard, but it's still to advanced for me. Where you say "let's define the number x..." what is that in plain English?
98Clubs Joined: Jun 3, 2010
• Posts: 1728
December 16th, 2013 at 9:09:07 AM permalink
Greasyjohn, lets assume the number of prime numbers is infinite.

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.
Some people need to reimagine their thinking.
speedycrap Joined: Oct 13, 2013
• Posts: 1246
December 16th, 2013 at 9:43:24 AM permalink
Numbers are infinite, then so is prime.
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.
AxiomOfChoice Joined: Sep 12, 2012
• Posts: 5761
December 16th, 2013 at 11:52:36 AM permalink
John, let me try to explain.

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.
Greasyjohn Joined: Dec 8, 2013
• Posts: 2172
December 16th, 2013 at 1:02:22 PM permalink
Thanks 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!
AxiomOfChoice Joined: Sep 12, 2012
• Posts: 5761
December 16th, 2013 at 1:13:14 PM permalink
Quote: Greasyjohn

Thanks 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.
pokerface Joined: May 9, 2010