Infinitely Many Primes?!

Prime numbers are one of the most fascinating aspects of Number Theory. Despite being one of the simplest to define, they have amazed mathematicians for centuries. In the post, we see, how one of the earliest theorems on prime numbers was proved by Euclid about 2000 years ago!

Prime Numbers: 

A natural number greater than 1, that is divisible only by 1 and itself is called a prime number. In other words, if ` p \in N`, `p > 1`  has only `1` and `p` as its factor, then the number `p` is called a prime number. For example `19` has no factors except `1` and itself. Thus it's a prime number. The first `20` prime numbers are listed below:

 ` 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29`

`31, 37, 41, 43, 47, 53, 59, 61, 67, 71`

Fig 1: The distribution of first 20 prime numbers

(In x-axis, 10 units represent the gap between two primes)

So Many Primes!

It's then exciting to know certain properties of these special numbers, isn't it? Let's then see a few notations, that will help us in this journey:

` a | b \rightarrow` `a` divides `b`

` \exists \rightarrow` There exists

So now we can now introduce our theorems. However, before being able to prove that there are infinitely many primes, we have to prove another theorem. We have our first theorem as follows, 

Theorem 1:  (Theorem of prime factorization) Every natural number except `1`, is a product of primes.

Proof: Consider any natural number `n \in \mathbb{N} `, greater than 1. Either `n` is prime, where there is nothing to proof, or it has factors between `1` and `n`. Consider the smallest factor `f`, ` 1 < f < n`. Then `f` is prime. For if `f` is not prime, then,

` \exists` ` f_{1}` ,  `1 < f_{1} < f` such that `f_{1}| f `

However, 

` f_{1}  |   f  `  &  `f  | n` ` \Rightarrow `  ` f_{1}  |  n`

But this contradicts our assumption that `f` is the smallest factor. Therefore, `f` has to be prime.

As `f` is prime, let `f  = p_{1}`, so that, 

` n = p_{1} \cdot n_{1} `

where `n_{1}` is either prime or composite `(n_{1} \ne 1)` . If `n_{1}` is prime, the job is done. If not, then we can again select the smallest factor of `n_{1}`, (let it be `p_{2}`) and write,

`n = p_{1}\cdot p_{2} \cdot n_{2}`

Again if `n_{2}` is not prime, we can repeat the same process. Repeating this way, we must reach, 

` n = p_{1}\cdot p_{2} \cdot p_{3}\cdot \cdot \cdot p_{k}`

where `n` is product of primes only. These primes `p_{i}` are not necessarily distinct, nor arranged in any particular order. In the standard form, this can be written as, 

` n = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot \cdot \cdot p_{k}^{α_{k}} `

where,  ` p_{1} < p_{2} < \cdot \cdot \cdot  < p_{k}` , and ` α_{i} > 0 `  for all  `i`

This process may be called the prime factorization of `n`.  Also note that any natural number `n` has only one these standard forms that is unique to it.

☐

Theorem-2: If `m | a + b` and if `m` divides either one of `a` and `b` individually, then it must divide both `a` and `b`. And if `m` divides only one of `a` and `b`, then it cannot divide `a + b`.

Proof: Suppose `m | a + b` and `m | a `, then we can write, 

`a + b = km`

`a = k_{1}m`

for some `k` and `k_{1} \in \mathbb{Z}` . We want to show that given these facts, `b` can also be shown to be product of `m` and some integer. See that, 

` b = km - k_{1}m`

` b = (k - k_{1})m `

As ` k - k_{1}` is also an integer, `m | b`. This proves the first part of the theorem.

The second part is more interesting. Let's again assume that ` m | a `. Then accordingly we must have ` a = k_{1}m` and since `m ∤ b `, there exists no `k_{2} \in \mathbb{Z}` such that `b = k_{2}m`. 

We will proceed with contradiction. Suppose `m | a + b ` so that ` a + b = km`. Again as ` a = k_{1}m`, it can be shown that, 

`b = k_{2}m`

where `k_{2} = k - k_{1} \in \mathbb{Z}`. But this contradicts the fact that there exists no such `k_{2}`. Therefore, `m ∤ a + b`.The proof is thus complete.

☐

Now that all the prerequisites are done and we can proceed to our final theorem to prove that there are infinitely many prime numbers. 

Theorem-3: (Euclid's 2nd Theorem) The number of primes in infinite.

Proof: Let `S` be the set of all prime numbers known to us. Say, `S` contains some `k` prime numbers in increasing order such that,

`p_{1} < p_{2}< \cdot \cdot \cdot < p_{k} `

Using these `k` prime numbers, we construct a new number `N`, 

`N = p_{1}p_{2}...p_{k} + 1`

None of the the prime numbers `p_{i} \in S` divides `N`. Hence `N` must be either one of the two:

1. `N` is a prime itself.

2. `N` is composite with a prime factor not on the list.

In either case, we are sure of another prime number `p_{k+1} \notin S`.  Thus it always possible to find a prime number not already in `S` . Since `k` can be indefinitely large, there are infinitely many prime numbers.

☐

There are also few other variations of the proof with a few tweaks, but the overall idea remains the same.

Conclusion:

With this dear readers, we touched one of the very earliest mathematical thoughts proved by sheer rigour and intuition. The prime numbers have been a subject of research for many centuries and yet their properties still amaze us today. One of the most famous contemporary problems The Riemann Hypothesis is estimated to provide new insights into their distribution on the number line. But even aside from all th fancy what's unique to the prime numbers is the beauty in their simplicity.

Prime Number Checker!:

Is your lucky number a prime? This tool below helps to check if a number is prime. Try it out!

 

Check for Prime:

(This checker may predict wrong results for numbers having more than 10 digits.)