How Do We Know That There Are Infinitely Many Prime Numbers?

There is a very famous theorem which says that there are infinitely many prime numbers. For people who are new to this, a prime number is a number that doesn’t have any divisors except for 1 and itself. For example, 11 is a prime number because it doesn’t have any divisors apart from 1 and 11. On the other hand, 12 is not a prime number because it is divisible by 1, 2, 3, 4, 6, and 12. Now how do we know that there are infinitely many primes? As numbers get bigger, they tend to have more divisors. So may be at some point, all the numbers can possibly start being composite and they will have a lot of divisors, right? We can delve into a deep mathematical proof to prove this, but let’s take a different route. Let’s see if we can prove this with logic, shall we?  

How do we begin?

Let’s set up the problem with some nice background here. If we list out the first few prime numbers, it will look something like this: 2, 3, 5, 7, 11, 13, etc. So now, the first question that comes to mind is whether or not this list will end? As in, is there a point after which we wouldn’t find any prime numbers? In this case, the biggest prime number would be a finite number. So we can also pose the same question in another way: What is the biggest prime number?

As we can see here, for composite numbers, the number of divisors keep increasing as the numbers keep getting bigger and bigger. For example, the number 10 has only 1 divisor (i.e. 5), where as the number 24 has 6 divisors (2, 3, 4, 6, 8, 12). The thing is that, as numbers get bigger, we have more numbers that are smaller than them. So the chances of them being the divisors are higher. So may be there is a point above which every number is divisible by some smaller number and is therefore not prime. It’s a possible scenario, right?

How do we go about proving something like this?

We are dealing with infinity here. As in, we are making a statement that involves infinity. As we know, things get very abstruse when we are dealing with infinity. We cannot ask a machine to check it for every possible number, right? It will never finish the task! So the brute force approach is out of question. This is where we use something called proof by contradiction.

Proof by contradiction is a popular technique used to prove results. What we will do is we are going to assume that the opposite is true, and then show that it leads to a fundamental contradiction. Then, we can assert that the opposite must be true. We are going to assume that we have a finite number of primes and see where it takes us.

Let the proof begin

So let’s say that we don’t have an infinite number of primes. This would imply that there is a largest prime number, after which all numbers are composite. We just don’t know what this number is, but we know that it exists. Let’s call this number ‘L’. So now, we have a list out all the prime numbers that exist: 2, 3, 5, 7, …, L.

Using this list, let’s define a new number in the following way:

M = (2 × 3 × 5 × 7 × 11 × ... × L) + 1

As we can see, this is a huge number, but it is still finite. Now, is ‘M’ a prime number? Well, obviously it cannot be a prime number because we just said that ‘L’ is the largest prime number that exists. So this means that M is a composite number. If M is a prime number, then L would cease to be the largest prime number. This would be a contradiction!

Why did we construct that big number?

Okay so we established that M is not a prime number. This would mean that M must be divisible by a prime number. Every composite number can factorized into its prime factors. For example, the number 18 can be written as 2 x 3 x 3. As we can see, both 2 and 3 are prime numbers. This holds true for every single composite number. Since we know M is not prime, it must be divisible by a prime number.

If we take a random prime number from our list {2, 3, 5, 7, …, L} and try to divide M, we will always be left with a remainder of 1. This is because the first term in M i.e. (2 x 3 x 5 x 7 x 11 x … x L) can divide every single prime number because it constructed by multiplying all of them. So after this, the second term i.e. 1 will always remain in the remainder. This holds true for every single prime number in our list.

Wait a minute, does this mean that M is not divisible by any prime number?

That can’t be right! We just said that M is a composite number, and every composite number is divisible by at least 1 prime number. But as we can see here, M is not divisible by any prime number. This means that M must be a prime number itself. But how is that possible? We said that L is the largest prime number that exists. Here, M is greater than L and we just concluded that M is a prime number. This is a contradiction!

Hence, we can never say that a given number is the largest prime number because we can always construct a bigger number that’s prime as well. The list of primes is infinitely long, thus proving our hypothesis.

———————————————————————————————————