We know that, when it comes to numbers, they keep stretching on into the endless abyss. The concept of infinity encompasses the fact that there is no end to it. However, does the same argument extend to primes as well? Prime numbers have the unique distinction of being numbers that have only one and itself as its only factors. Can numbers with such a self-limiting property stretch on to infinity and beyond? There are multiple proofs we will look into, the first proof of which is the most elegant of them all.
Proof of Infinite Primes
Euclid was a Greek mathematician who lived in Alexandria and Hellenistic Egypt. He is commonly referred to as the ‘father of geometry.’ He published the fundamental theorem in number theory that there is an infinite number of prime numbers. In his book the Elements, he was able to give a proof to the following theorem.
Now to begin proving the theorem, let’s first assume that there is only a finite number of primes available. Let us denote this set of finite prime numbers with the notation n. We denote each prime number in the following manner:
p1, p2, p3, p4, p5, p6, p7……pn
Now, let us construct a new number such that we multiply each prime in the above set of finite primes. After the multiplication, we add one to the product obtained. Now the number obtained can be named Q. The number we obtain is the following:
Q= p1 xp2 xp3 xp4 xp5 xp6 xp7x…xpn +1
Q is larger than the set of finite primes we defined. Also, since the set of primes already contains the finite number of primes (which we assumed), then Q cannot be prime. Therefore, the number Q should be able to divide from the set of finite numbers. Let’s assume that it is one of the primes in the set of primes pm (where m is anywhere between 1 and n). However, when we divide Q by pm, we end up getting the remainder 1. Now, this leads us to a contradiction, which implies that the initial assumption that there are a finite number of prime numbers is incorrect. This proves that there is an infinite number of primes.
Although Euclid may have produced the first elegant proof, there have been other mathematicians that have proved the same in different ways. Christian Goldbach was a German mathematician who studied law. He was cleverly able to prove that there was an infinite number of prime numbers by using the Fermat number. The Fermat number was named after the mathematician Pierre De Fermat who first studied them. The Fermat theorem is a positive integer of the form:
He used the above Fermat number as a Lemma. In mathematics, a lemma can be defined as a helping theorem that is used as the foundation to prove a large theorem or conjecture. Now, to prove that there is an infinite number of prime numbers, let’s choose a prime divisor for pn for each Fermat number Fn. With the aid of the lemma, we know that these primes are all distinct, showing that there are an infinite number of primes.
Note that any sequence that is pairwise relatively prime will work in this proof. This type of sequence is easy to construct. For example, choose relatively prime integers a and b, then define a as follows.
a4=a1x a2x a3+b,
This includes both the Fermat numbers (with a=1, b=2) and Sylvester’s sequence (with a=1, b=2):
a1=2 and an+1= an2-an+1.
The proof only needs a sequence that has a subsequence, which is pairwise relatively prime. There are many famous theorems that have used the infinite theorem to prove other a as the basis for their proof. Famous mathematicians like Paul Erdos and Euler have used the infinite prime theorem to make a great deal of pivotal and important progress in the field of number theory.