The prime natural numbers are those which have no divisors other than 1 and themselves. They exist in infinite number by Euclid’s theorem, which is not difficult to prove.

1.Prime numbers

1.1.Divisors and primes

A prime number is a non-zero natural number (see What is a natural number?) \(p\) different from \(1\) and whose only divisors are \(1\) and \(p\) itself. But what is a divisor? A divisor of a natural number \(n\) is a natural number \(d\) such that \(d\) divides \(n\)… that is, such that \(n\) is a multiple of \(d\). In other words, a divisor \(d\) of a natural number \(n\) is a number having the property that “\(d\) multiplied by a certain number \(k\) equals \(n\)”. Mathematically, this is expressed rigorously by “there exists a natural number \(k\) such that \(n=d\times k\)”. A prime number is therefore a natural number \(p\neq 0,1\) for which there is no other decomposition of \(p\) in the form of a product \(d\times k\), than the so-called “trivial” decompositions which are \(p=1\times p\) and \(p=p\times 1\).

1.2.Testing whether a number is prime

Among the first prime numbers, one could quote \(2\), \(3\), \(5\), \(7\), \(11\), \(13\), \(17\), \(19\)… In order to know that these numbers are prime, it is necessary to be able to prove it; this is possible by carrying out for example Euclidean divisions. In general, there is a criterion to test if a number \(n\) is prime: if it is not prime, there exists a divisor of \(n\) which is a prime number \(p\) (what is called a prime factor) and which is smaller than \(\sqrt n\). To know if a given number \(n\) is prime, it is thus enough to test its divisibility by all the prime numbers \(p\) already known and smaller than \(\sqrt n\). If none of these divides \(n\), then \(n\) is prime! For example, to know if \(97\) is prime, we notice that \(9^2=81<97<10^2=100\), so \(9<\sqrt{97}<10\): we test the prime numbers between \(1\) and \(9\), i.e. \(2,3,5\) and \(7\), and none divides \(97\): this one is therefore prime.

The first nine prime numbers as they are distributed on the mysterious Ulam spiral.

2.Euclid’s theorem

2.1.The set of prime numbers is infinite

It seems that one can always, given a prime number \(p\), find a prime number strictly greater than \(p\). This is in fact a consequence of a famous theorem of antiquity, found in Euclid’s Elements, which states that there are always more primes than a given (finite) set of primes. In the language of modern mathematics, we would say that there are infinitely many primes, or that the set of primes is infinite. This means that it is not possible to “count” them, i.e. to find a natural number \(n\) which allows them to be written as a list \(p_1,p_2,\ldots,p_n\) (see Finiteness and Mathematical Infinity: Comparing and Counting).

2.2.Proving Euclid’s theorem

This theorem is not very difficult to prove, and we propose here an outline of the demonstration. As a prerequisite, we need to admit three simple arithmetical facts:

• Fact 1: Any natural number \(n\geq 2\) has a prime factor (a divisor which is a prime number)
• Fact 2: If \(a, b, c\) are three natural numbers such that \(a\leq b\), \(c\neq 0\) and \(c\) divides \(a\) and \(b\), then \(c\) divides \(b-a\) (in this context, the natural number \(x\) such that \(a+x=b\))
• Fact 3: If \(d\) is a divisor of a non-zero natural number \(n\), then \(d\leq n\).

From the definition of the product of \(n\) numbers by induction, the proof of the theorem can be done according to the following scheme:

• We reason by contradiction by supposing that there is only a finite number of primes, \(p_1,\ldots,p_n\)
• Consider the number \(m=p_1\times \ldots \times p_n+1\), which is greater than \(2\) and thus has by Fact 1 a prime factor \(q\), which is necessarily one of the \(p_i\)’s
• Then, \(q\) is at the same time a divisor of the product \(p_1\times \ldots\times p_n\) of the \(p_i\)’s and of \(m\), therefore \(q\) divides \(1=m-p_1\times \ldots\times p_n\) by Fact 2
• By Fact 3, we then have \(q\leq 1\), but by definition, the prime number \(q\) is greater than \(2\), so we get \(2\leq 1\), which is a contradiction !
• By reductio ad absurdum (reduction to the absurd), we deduce that the initial hypothesis is false, in other words that the set of prime numbers is infinite.

2.3.Corollary: the prime numbers are “cofinal” in the set \(\mathbb N\)

From Euclid’s theorem, we can deduce a more “visual” property of the infinity of the primes: whatever the natural number \(n\), we can always find a prime number \(p\) “strictly greater than \(n\)”, i.e. such that \(n<p\). In fact, the infinite subsets of \(\mathbb N\) are exactly those which possess this property, which can be demonstrated with elementary methods of set theory.