Among the pairs of integers $(a, b)$ such that $1 \leqslant a \leqslant b \leqslant 5$, how many are there for which $a$ and $b$ are coprime?

Moreover, there are also other numbers, much better known to the general public, which have remarkable divisibility properties: these are the prime numbers.

## Definition 2.2.12.

We say that an integer $n$ is prime if $n$ has exactly 2 positive divisors, which are 1 and $n$. Otherwise, we say that $n$ is composite.

## Remark 2.2.13.

The integer 1 is therefore not prime!

From the definition of prime numbers, the following crucial results quickly follow.

## Theorem 2.2.14.

Let $n$ be an integer and $p$ a prime number. Either $p$ divides $n$, or $p$ is coprime with $n$, these two cases being mutually exclusive.

Proof. First, if $p$ divides $n$, then $p$ is a common divisor of $p$ and $n$, so $p \wedge n \neq 1$, which shows that $p$ and $n$ are not coprime. Now suppose that $p$ does not divide $n$, and let $d = p \wedge n$. Since $d$ divides $p$, we know that $d = 1$ or $d = p$. Since $d$ divides $n$, it follows that $d \neq p$, and therefore $d = 1$.

## Theorem 2.2.15.

Let $n$ be an integer such that $n \geqslant 2$, and let $p$ be the smallest divisor of $n$ such that $p \geqslant 2$. Then the integer $p$ is a prime number.

Proof. Since $p \geqslant 2$, we already know that 1 and $p$ are two distinct divisors of $p$. Now let $d$ be a divisor of $p$. According to Theorem 2.2.3, and since $p$ divides $n$, we know that $d$ also divides $n$. By the minimality of $p$, we deduce that $d = 1$ or $d = p$, which means that $p$ is prime.

It is therefore very important to be able to detect whether an integer $n$ is prime or not. Achieving this efficiently is a difficult question, which will be the subject of the course on "primality tests" given to group D. However, there is already an ancient and relatively efficient method when $n$ is small: it is the Sieve of Eratosthenes, which allows identifying the set of prime numbers less than or equal to $n$.

Like the Euclidean algorithm, it is important to show that the Sieve of Eratosthenes returns the correct list of prime numbers $p \leqslant n$.

## Theorem 2.2.16.

The list of integers returned by the Sieve of Eratosthenes is indeed the list of prime numbers $p \leqslant n$.

```
Algorithm 2: Sieve of Eratosthenes
    Argument(s): \(n \quad \triangleright\) We want to identify the prime numbers \(p \leqslant n\)
    write all integers from 2 to \(n\)
    as we go, we will either cross them out or circle them
    while there is an integer \(p \leqslant \sqrt{n}\) that is neither crossed out nor circled:
        choose the smallest such integer \(p\) and circle it
        cross out all multiples of \(p\) between \(p^{2}\) and \(n\) that were not already crossed out
    return the list of integers that were not crossed out (even those that are not circled)
```

Proof. Our proof will proceed by induction on $n$. First, if $n = 1$, the result is obvious. We therefore assume that $n \geqslant 2$ and that, if we run the Sieve of Eratosthenes with $n-1$ as the argument, it returns the correct list of prime numbers $p \leqslant n-1$. Let's then see how it behaves when we give it $n$ as the argument.

Already, it is clear that the integers $k \leqslant n-1$ that we will cross out are the same, whether the argument of the algorithm is $n-1$ or $n$. It remains to show that we will cross out $n$ if it is composite, but not if it is prime.

If $n$ is prime, we will clearly never cross it out. We therefore treat the case where $n$ is composite. Let $p$ then be its smallest divisor such that $p \geqslant 2$. Theorem 2.2.15 shows that $p$ is prime. Moreover, since $n = p \times (n / p)$ and $p < n$, we know that $n / p$ is a divisor of $n$ greater than or equal to 2, so $n / p \geqslant p$. This shows that $p \leqslant \sqrt{n}$.

Since $p$ is prime, we will never cross it out, so we will eventually circle it. By doing so, and since $n \geqslant p^{2}$, we will necessarily cross out $n$. This concludes the proof of the theorem.
It suffices to list the positive divisors of each integer between 1 and 5: each integer $n \in\{1,2,3,5\}$ is only divisible by 1 and itself, whereas 4 is divisible by 1, 2, and 4. Consequently, if $1 \leqslant a \leqslant b \leqslant 5$, the integer $a \wedge b$ is different from 1 if and only if $a=b \geqslant 2$ or if $(a, b)=(2,4)$.

Now, there are $5+4+3+2+1=15$ pairs $(a, b)$ such that $1 \leqslant a \leqslant b \leqslant 5$. Out of these 15 pairs, we have just counted 5 such that $a \wedge b \neq 1$. Therefore, there are 10 pairs such that $a$ and $b$ are coprime.