Infinitely Many Prime Numbers by Euclid

To me, prime numbers are really interesting in terms of their position as the building blocks of other numbers. According to the Fundamental Theorem of Arithmetic, every positive integer N can be written as a product of P1, P2, P3, …, and Pk where Pi are all prime numbers.

The question, however, lies on whether the number of primes is infinite. Well, the answer is yes. Euclid proved that there are infinitely many prime numbers and his proof is shown below.

Suppose we have a list L consisting of all the prime numbers. Let’s multiply all of the prime numbers in L and add 1 to the result. Mathematically, we can write it like the following:

L = p1 . p2 . p3 ... where pi are all prime numbers
N = L + 1

After the above step, we now have two possible outcomes. The first one is that N is a prime number. If so, then our initial hypothesis telling that L has already included all the primes is wrong as we still have a new prime number N that is not in the list.

Meanwhile, the second possible outcome is that N is not a prime number. In this case, we may say that N has a prime factor since the Fundamental Theorem of Arithmetic states that all positive integers have a unique prime factorization. Let’s call this prime factor k. The thing is that k may or may not be in our list L. If k is in the list, then N should not be divisible by k since the division will have the remaining 1. To make it more precise, N is not divisible by any of prime numbers in L. Therefore, there must be a prime factor outside L that divides N. This prime factor may or may not be N itself. Based on this fact, we know that we can always find another prime number outside our list L.

Q.E.D