Euclid's theorem on prime numbers

Continuing with our story about prime numbers, today we will prove that there exists an infinite number of primes. This is called the Euclid's theorem on prime numbers. This theorem has a very simple proof but it is probably one of the most beautiful proofs ever in mathematics.

To prove that there are infinitely many prime numbers, we will show that for any sequence of prime numbers $p_1$, $p_2$, ..., $p_k$, we can find another prime number that is not in this list.

What we do is we construct this number: $n = p_1 p_2 \dots p_k + 1$.

Now, clearly, $n$ must have a prime divisor. But since $n$ is not divisible by any of the prime numbers $p_i$, the prime divisor of $n$ must be a new prime number that is not in the above list of primes.

So, for any finite sequence of prime numbers, we can find another prime number. This proves that there must be an infinite number of primes.

This proof is so simple, yet, it is so beautiful! Let us use this technique to solve some similar problems.

Problem 1. Prove that there are infinitely many prime numbers of the form $4N+3$.

We know that $2$ is the only even prime number, all other primes are odd numbers. An odd prime number is either of the form $4N+1$, or of the form $4N+3$. To prove that there exists an infinite number of primes of the form $4N+3$, we will use a similar argument as above. That is, for any sequence of prime numbers $p_1$, $p_2$, ..., $p_k$ of the form $4N+3$, we will show that there exists another prime number of the form $4N+3$ that is not in the list.

We choose $n = 4 p_1 p_2 \dots p_k - 1$.

This number $n$ must have a prime divisor of the form $4N+3$. Why it that? The reason is, because $n$ is an odd number greater than $1$, if $n$ does not have any prime divisor of the form $4N+3$ then all prime divisors of $n$ must be of the form $4N+1$. Thus, $n$ is a product of numbers of the form $4N+1$. It is easy to see that a product of numbers of the form $4N+1$ is a number of the form $4N+1$. Therefore,  $n$ is a number of the form $4N+1$, and this is a contradiction.

We have shown that $n$ must have a prime divisor $p$ which is of the form $4N+3$. Next, since $n$ is not divisible by any of the prime numbers $p_i$, we conclude that $p \neq p_i$. Let us now write down the proof.

Solution to the Problem 1. To prove that there exists infinitely many prime numbers of the form $4N+3$, we show that for any sequence of prime numbers $p_1$, $p_2$, ..., $p_k$ of the form $4N+3$, there exists another prime number which is also of the form $4N+3$.

Indeed, take $n = 4 p_1 p_2 \dots p_k - 1$.

We claim that $n$ must have a prime divisor of the form $4N+3$. This is because if all prime divisors of $n$ are of the form $4N+1$ then as a product of numbers of the form $4N+1$, $n$ must also be of the form $4N+1$, which is a contradiction.

So, $n$ must have a prime divisor $p$ which is of the form $4N+3$. Since $n$ is not divisible by any of the prime numbers $p_i$, we must have $p \neq p_i$.

Thus, for any finite sequence of prime numbers of the form $4N+3$, we can find another prime number which is also of the form $4N+3$, so there must be an infinite number of primes of the form $4N+3$. $\blacksquare$

Problem 2.  Prove that there are infinitely many prime numbers of the form $4N+1$.

To follow the above argument we would choose $n = 4 p_1 p_2 \dots p_k + 1$ and try to prove that $n$ has a prime divisor of the form $4N+1$. However, a closer look tells us that this is not achievable. The reason is that a product of two numbers of the form $4N+3$ is a number of the form $4N+1$. Therefore, $n$ could be a product of two prime numbers of the form $4N+3$ and it will make $n$ a number of the form $4N+1$, but yet, $n$ will not have any prime divisors of the form $4N+1$. We need to find another proof.

We will use $n = 4 p_1^2 p_2^2 \dots p_k^2 + 1$. To show that $n$ has a prime divisor of the form $4N+1$, we use the following useful fact.

Lemma. For any $x$, the number $x^2 + 1$ has no prime divisors of the form $4N+3$.

To prove this lemma, we need to use the Fermat's little theorem. You can read more about the Fermat's little theorem in this post "modulo - Part 5".

The Fermat's little theorem asserts that, for any prime number $p$, and for any integer $a$ that is not divisible by $p$, $$a^{p-1} = 1 \pmod{p}.$$

We prove the lemma by contradiction. First, we assume that $x^2+1$ has a prime divisor $p=4N+3$. Thus obtaining $$x^2 = -1 \pmod{p}.$$ It follows that $$x^{4N+2} = (x^2)^{2N+1} = (-1)^{2N+1} = -1 \pmod{p}.$$

However, by Fermat's little theorem, we have $$x^{4N+2} = 1 \pmod{p}.$$

So $1=-1 \pmod{p}$, or equivalently, $2=0 \pmod{p}$. This is a contradiction, so the lemma is proved. $\blacksquare$

Solution to the Problem 2. To prove that there exists infinitely many prime numbers of the form $4N+1$, we show that for any sequence of prime numbers $p_1$, $p_2$, ..., $p_k$ of the form $4N+1$, there exists another prime number of the form $4N+1$ which is not in the list.

Indeed, take $n = 4 p_1^2 p_2^2 \dots p_k^2 + 1$.

This number $n$ is of the form $x^2+1$. By the lemma that we have just proved, $n$ does not have any prime divisor of the form $4N+3$. Since $n$ is an odd number, all prime divisors of $n$ must be of the form $4N+1$. We also easily see that none of the prime numbers $p_i$ in the list is a divisor of $n$. Thus, we have found new prime numbers of the form $4N+1$.

We have shown that for any finite sequence of prime numbers of the form $4N+1$, we can find other prime numbers of the form $4N+1$, therefore, there must exist an infinite number of primes of the form $4N+1$. $\blacksquare$

Before we stop, let us just remark that the above two problems are actually two special cases of a general theorem. This is called the Dirichlet's theorem on arithmetic progressions. The Dirichlet's theorem asserts that for any two coprime numbers $a$ and $b$, there exists an infinite number of primes of the form $aN+b$.

Let us stop here for now. See you again in the next post.

Homework.

1. Prove that there are infinitely many prime numbers of the form $6N+1$.

2. Prove that there are infinitely many prime numbers of the form $6N+5$.

3. Choose some other values of $a$ and $b$, and prove that there exists an infinite number of primes of the form $aN+b$.