A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.
In this series of articles, I will cover various topics regarding prime numbers, such as
- Are there infinite prime numbers? why?
- How can we find prime numbers?
- Open problems related to primes
Are there infinite prime numbers? why?
Short answer — Yes there are.
There are many proofs that show exactly why there must be infinite prime numbers. The most famous, and in my opinion the easiest to understand, is Euclid’s proof.
Before moving on to Euclid’s proof, it is worth mentioning the Fundamental Theorem of Arithmetic (also known as Unique Factorization Theorem).
This theorem states that every natural number greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors.
For example, 12 = 3 ⋅ 2 ⋅ 2 = 3 ⋅ 2²
6 = 3 ⋅ 2
25 = 5²
Euclid proved the infinity of primes by contradiction.
He started by assuming that there is a finite amount of primes and notated them P₁, P₂, …, Pₙ.
Now he defined two new numbers
P=P₁ ⋅ P₂ ⋅ … ⋅ Pₙ
Now there are two options regarding the ‘status’ of q, is q a prime or not?
If q is a prime, then we definitely missed a prime in our list and now we have n+1 primes instead of n.
If q is not a prime, then from the Fundamental Theorem of Arithmetic we know that some prime factor p divides q.
If p is not on our list, then again we found a new prime and now we have n+1 primes.
If p is on our list, we can tell that it divides P from the way we constructed it (the product of all primes in the list).
Since p divides both P and q=P+1, we know that p also divides the difference of the two numbers, which means that p divides P+1-P =1.
Since no prime number divides 1, p is not on the list, which means that there’s at least one prime out of the list — n+1 primes.
As I mentioned before, in my opinion, Euclid’s proof is the easiest to understand, especially if you’re not well-versed in mathematics, but now I am going to introduce another proof of the infinitude of primes, which is shorter and I also find it to be the most appealing, at least in my eyes.
Let π(x) be a prime-counting function.
Wait, what is a prime-counting function? A prime-counting function is a function counting the number of prime numbers less than or equal to some real number x.
For example, π(10.124) = 4 considering the primes 2,3,5,7.
The Prime Number Theorem suggests that
Trying to make it more intuitive, we can say that π(x) “behaves” like x/ln(x) when x is approaching infinity — there’s an asymptotic ‘equality’.
But we already know that
And that’s it, the prime-counting function is approaching infinity when x is approaching infinity — there are infinite primes.
Before you go, I want to show you a beautiful visualization I made (it’s not beautiful because I made it, it’s because of the primes).
I animated the first 10k prime number in a polar coordinate system.
Here’s the code that I wrote to create this visualization
In this part of the series on prime numbers, we learned why there are an infinite amount of prime numbers looking at two different proofs.
In the next part, I wish to discuss computational methods to find primes.