Primes are infinite: an alternative proof

The great Euclid came up with one of the oldest and most acclaimed mathematical proofs of all times: the proof that there is no upper-bound limit to the set of prime numbers. Or, put in a different way, prime numbers are infinite.

There is no question whatsoever that the proof is not only correct beyond any doubt but also marvelously simple to understand.

However, despite all the brilliance in the proof, there are two aspects of it that slightly bothered some (very picky) mathematicians out there. 

The first one is that there is an underlying assumption (more like an insinuation, a hint) that not only the largest prime needs to be known for the proof to work, but also all the other primes too. I can see why it kind of bothers some purists, although the vast majority of mathematicians will argue that such assumption is complete non-sense, that the proof is designed to work even without that assumption in place, which I understand. But in any case, the controversy is there, even if it bothers only a handful of hardcore purists. The second aspect is that the proof is not constructed using building blocks, such as theorems and lemmas. It stands by itself. Some might argue that the “standing by itself” is indeed what makes the proof so beautiful and easy to grasp, even by laymen. But again, few hardcore mathematicians would have loved if the proof was more traditional, more formal, where building blocks (theorems) were proposed and proved, and eventually they would all elegantly fit together to construct the final (and often surprising) attack to the problem.

There is an alternative proof to Euclid’s (genius, one more time!) proof. Which hopefully addresses all concerns aforementioned.

Similarly to Euclid’s, the proof that we’re going to present is also a proof-by-contradiction: we’re going to assume that somehow the largest prime number has been discovered by a super-computer at a fancy university or by hackers who might have stolen hundreds of thousands of virtual machines in some cloud computing substrate, and jotted down some distributed code to find the largest and very last prime. We’ll call this prime N. N could very well be 2^(999,999,999,999,999,999,999,999,999) – 1. Assume that this is the last prime, and with the set of prime numbers {2, 3, …, N}, all the other positive natural numbers can be derived. That’s a bold assumption. We’ll prove that it is wrong.

Alright, the first thing that we’ll do is to start with a theorem that, at a first glance, seems completely unrelated to the problem that we’re trying to solve, but that’s the beauty of it: this theorem will be invaluable when building the final attack to prove that such N cannot, and does not, exist. Here we go (red herring note: we call the theorems below theorems because there will be proofs associated with them. A claim without a proof is simply a conjecture. A conjecture for which there is strong believe that it is indeed correct (however no proof has been found for it yet) becomes a hypothesis):

Theorem #1: a positive natural number and its immediate successor share only the number 1 (one) as their common divisor.

Proof of theorem #1: basically theorem #1 is claiming that two consecutive natural positive numbers cannot have any common divisor other than the number 1 itself. For example, what’s the common divisors of 6 and 7? That would be 1. What about 100 and 101? Again, 1. How about 2^1000 and 2^1000+1? Again, 1. It is intuitive, but mathematics has no room for intuition or opinions, hence we need to formally proof this theorem. For that, let’s assume that two consecutive numbers share a common divisor which we’ll name it “d”. Mathematically we shall have:

1.       n = d * k1 (equation 1)

2.       n + 1 = d * k2 (equation 2)

So the number (n) and its successor (n+1) share the same common divisor d. Note that {n, d, k1, k2} must be all natural positive numbers, and k1 does not have to be the same as k2. Let’s subtract equation (2) From equation (1):

n + 1 – n = d * k2 - d * k1

1 = d * (k2 – k1)

d = 1 / (k2 – k1)

The last equation above that we ended up with is crucial to complete the proof of theorem #1. Since d must be a natural positive number, it then forces (k2 – k1) to be 1. If (k2 – k1) is not 1, then d will end up being either a fraction or negative, which violates the assumption that d was a natural positive number to begin with. d must be 1. Hence, the only divisor that n and n+1 share is 1. The proof is complete.

We can now use theorem #1 as a building block whenever we feel appropriate. Theorem #1 has become a function, an API implemented and certified by a programming language, which we can use without worrying whether or not it will work. It will always work, because it has been mathematically proved.

Now we can finally start the construction of the proof that a final, largest prime number N is impossible. Here we go:

Theorem #2: for any prime number N, there will always be a prime number N_next such that N_next > N.

Proof of theorem #2: the proof for theorem #1 was fundamentally a construction proof: we determined the solution for a set of equations. The strategy here, as I mentioned before, will be different: we’ll use a contradiction approach. Let’s imagine that indeed N is the largest prime. And here comes the first great insight about this alternative proof: let M = N! + 1. Bingo!!! Without knowing all the previous primes, we just, out of the blue, constructed a new, perfectly valid number M, which happens to be the factorial of N plus one (yes, a big number, but that’s ok). The rest of the proof analyzes the properties of M. We have two cases that M can fall onto:

Case 1: M is prime. Well that’s a problem from the get-go then. If M is prime, and knowing that M is greater than N, it already demolishes the assumption that N is the largest number, and it completes the proof since we found a prime that is larger than N.

Case 2: M is not prime. Ok, that’s the most plausible and interesting case. Sure, M is a big number, bigger than N, but not a prime. Let’s see what this means. If M is not a prime (also known as composite number), it must be divisible by a prime. Hence M = a*b, where let’s say a is a prime. Now… out of nowhere, to help with the attack, comes “theorem #1”!!!! Using theorem #1 we know that two consecutive numbers only share the number 1 as their unique common divisor. Look at these two numbers:

 N!

 N!+1

By the way, the second number is M. But N! is simply the product of all numbers up to N. N! = 1*2*3*4*….*N. Since M cannot have none of these numbers as divisors (but the number 1 only), then we have a problem. Basically we’re unable to find a prime number less than or equal to N that divides M. If there was such a number, say 7, then it would violate theorem #1 since 7 is a divisor of N! and 7 would also be a divisor of N!+1. This is a big problem, and a lethal one, because now there is only one explanation: since M is composite, there must be a prime number p that divides M. p cannot be in the set {1, 2, 3, 4, 5, …., N-1, N} due to theorem #1. The only explanation is that p must be a prime number greater than N. Therefore, and again, even for case 2, we have determined the existence of a prime number p greater than N.

Hence, either N_next will be equal to N!+1, if N!+1 is prime, or N_next will be the number p, a prime number that we proved exists and it is greater than N. This completes the proof of theorem #2.

Let's exemplify the two cases above:

Example Case 1: suppose that N = 3. Therefore, M = 3! + 1 = 7. M is prime, and greater than N.

Example Case 2: suppose that N = 5. Therefore, M = 5! + 1 = 121. M is composite, and M = 11 * 11. 11 is prime, and hence p = 11. p is prime, and greater than N.

Primes are wonderful, they are a gift from the Gods to humans so that we can better understand nature and we can keep evolving our intellectual horsepower. Many important questions are being answered for primes, such as Primes is in P, the Goldbach’s weak conjecture, and the finite gaps between consecutive primes. But many are still unknown, such as Goldbach’s conjecture, the twin prime conjecture and the Riemann Hypothesis. It will be fascinating to see these conjectures and hypothesis being finally proved. Or disproved.

Regards,

Marcelo