The prime numbers are one of those basic, yet mysterious, sets in mathematics, that while we know much about them, there are still many interesting open questions waiting to be answered, including probably the most well known conjecture in mathematics – the Riemann conjecture.

While this conjecture, and the attempts at its solution, use very advanced mathematics, even the most basic questions about the prime numbers already have many interesting results and lead to interesting tools, and in this post and the next two (here and here), we will try to understand some of these just by trying to “count” primes.

## What is so special about primes?

Prime numbers have several definitions, though the one most people are familiar with is integers which are only divisible by and . Another equivalent definition is as follows: If are any 3 integers, where divides or , then divides the product . Using the notation for divides , this claim can be written as

Another definition for a prime number is an integer for which the converse is true as well, namely

Definition: An integer is calledprimeif for any two integers we have:

For example, for , saying that is what we call is even, and the primality of means that if is even, then either or is even. And for a more specific example, is even and in each of the decompositions , at least one of the factors is even.

As definitions go, this is quite a short one, but as in most cases, the definition in itself is not the important part, but rather what we can do with it. As for the prime numbers, this definition gives us one of the most basic results, on probably the most important set of numbers – the integers:

THEOREM: Every integer can be written as a product of prime numbers, and more over, up to the plus\minus signs and the order of the primes, this product is unique.

To understand the uniqueness part above, consider the example of . There are four ways to write it is product of primes:

.

While these are indeed 4 different ways to write the product, essentially we think of them as the same – we just choose the order of and , and choose their signs.

In particular, when restricting our attention to positive integers we get this equivalent result:

THEOREM:Let be the set of all primes, ordered in increasing manner. Then for any positive integer , there are unique nonnegative integers , almost all of which are zero, such that .

Note that the fact that almost all of the are zero, implies that is a finite product. When all the powers are zero, the product is and for our example from above, the product is .

The integers is one of the most important sets out there, and the theorem above basically tells us that multiplicatively the prime are the building blocks of this set. To define an integer we only need to choose which primes are “in it” and how many times each of them appear. Now, that we know why the prime numbers are so important we can start asking basic questions about them, and the first question will be how large is the set of prime numbers?

## A proof from the book

If we are given an integer , we can check if it is prime by simply going over all of and see if . In particular, if we want to count all the primes we can do it in a finite amount of time (or aternatively, we can write a program and let a computer do it). But how can we count all of the primes, namely find the size of , and does it really have a finite size, or is it infinite? To answer this, it will take more than a simple prime counting algorithm.

In order to do this, Euclid found a very simple proof showing that there are infinitely many primes (and this was all the way back to around 300 BC !).

**THEOREM**: There are infinitely many primes

**PROOF** (Euclid) :

We start with any finite set of primes and we show that there are always other primes outside this set.

The idea is to use the relation between addition and multiplication inside the integers. The primes are defined multiplicatively, so we first multiply all of them to get a number which “contains” all of them, namely . We then use the addition operation to “break” this property, and we claim that isn’t divisible by any of these primes. Indeed, if for some prime in our set and an integer , then

.

But is not divisible by numbers strictly larger than , and in particular prime numbers like .

Using the fact that every integer is a product of prime numbers, we know that there is some prime dividing , and it is not in , which is exactly want we wanted to show.

## The distribution of primes

Now that we know that there are infinitely many primes, we can look for finer details about this set. Since its importance comes from its role inside the set of integers, we can ask how it looks as a subset. Let us start with the usual way people view the integers by writing them in the 10 columns we all know from elementary school, corresponding to the unit digit.

Just looking at this picture, we can already see (=conjecture!) some interesting phenomena.

- The columns for the digits 0, 4, 6 and 8 don’t have any prime numbers.
- The columns for the digits 2 and 5 have exactly one prime.
- The columns for the digits 1, 3, 7 and 9 have a lot of primes – maybe infinite?
- Also, if we look on a larger version of this table, it seems that the columns for 1, 3, 7, and 9 have the same number of primes.

The first two claims above are quite easy to prove. First we should note that the digits and from the first two claims above, are exactly those that have a non trivial common divisor with (which can be or ).

Numbers which have a unit digit , are exactly those that we can write as . If we assume that has a nontrivial common divisor with , for example if is even, then the numbers with unit digit can be written as

All of these numbers are divisible by 2, and by definition there is exactly one such (positive) prime – the number 2. So unless and , the number cannot be prime. In particular we get that the columns for do not have any prime number, and the column for has exactly one prime. The same goes for the column with .

Here we used 10 columns because we are used to the 10 digit writing, but in general we can use any number of columns and ask if the ‘th column in it has zero or one prime. The same idea from above can be easily generalized to the following:

THEOREM: Let be an integer and be another integer. If and have a nontrivial common divisor, then contains exactly one prime if is prime, or zero primes otherwise.

Recall the we say that the numbers are **equivalent mod **and write , or if they have the same remainder when divided by (or equivalently ). For example, saying that the unit digit of is 2, is the same as saying that . Also, two numbers are called **coprime** if they their greatest common divisor (gcd) is 1. With this notation, the theorem above can be written as:

THEOREM: Let be integers which are not coprime. Then the number of primes such that is either 1 if is prime and otherwise.

Our other two observations relate to the case where and are coprime, in which case we want to show that there are infinitely many primes, and there are more or less the same number is each of the columns. This first claim is usually known as Dirichlet’s theorem for prime numbers in arithmetic progression, and our final goal for these posts is to give most of the intuition and tools needed to prove it, and some intuition why the second claim holds as well.

## Euclid’s proof revisited

Can we extend Euclid’s proof to show that there are infinitely many primes in the case of coprimality?

The simplest case is with and , or in other words we want to show that there are infinitely many odd primes. This is of course simple, because we already know that there are infinitely many primes and only one of them, , is even, so the rest are odd.

The first non trivial case is when and . Fixing, for example, , we can start as before with a finite set of primes which are mod and consider the product . There is still some prime which divides and it cannot be one of the , but unlike before, we don’t know that it also equals to mod . For example, for the first 3 such primes we get , where and .

We already see that it becomes more complicated, but there is a trick that can help here. Consider instead the number . It is also easy to check that it is not divisible by any of the and by . It might still be divisible by only primes which are mod . Fortunately, we also get automatically that , and you can take it as an exercise to show that the product of numbers which are mod is also mod . Thus, we conclude that has at least one factor which is mode and it is not one of the , which is exactly what we wanted.

This trick is interesting in itself, and relates to the structure of the group of units mod (which I will not go into any further here), but already becomes much harder when trying to adapt it to the case of primes which are mod , not to mention when is larger. Furthermore, this type of proof doesn’t let us compare between the primes which are mod or mod . In order to do this next step we need to revisit the proof that there are infinitely many primes, but this time use Euler’s approach, and we shall do it in the next post.