There are infinite Prime Numbers

Consider the below statement

There is an Infinite number of Prime Numbers.

I know you guys will think that it is obvious.
But if you think deep, you will notice that it is not straightforward because as the number increases, the density of the prime number decreases. If the number is large enough, then we may not get any prime number after that. Moreover, for large numbers, the chances that it has a factor are more because more numbers are candidates for its factor.

How to prove the infiniteness of prime numbers?

There are many methods, but the one I love most is Euclid's method. It is based on the Proof By Contradiction method.

It follows as following.

• Assume there is a finite number of prime numbers. Then We can list down all the prime numbers as

{p1, p2, p3 ... pn}

, where pn is the largest prime number. Note that the size of the list is finite.

• Now consider a new no. N as

N = p1 * p2 * p3 ... * pn + 1

• We can see that N is greater than pn , (largest prime number in the above list).
• For N, either of the two cases is true

1. It is a prime number
2. It is a composite number

• If N is a prime number: We got a new prime that was not included in the list.
• If N is a composite number: We can express it as the product of primes. But we can see N is not divisible by either of p1 or p2 .... or pn. So, if N is a composite number, then there must exist a prime factor of N which is not already in the list.

In both cases, we can get new prime numbers that are not on the list.

So our assumption that prime numbers are finite is wrong.

So there are an infinite number of primes

Thanks for Reading. Follow me for amazing content.