What can be said about a number $n$ that has an odd number of divisors?
We can group the divisors of $n$ in pairs $(d, n / d)$. If $n$ is not a square, we always have $d \neq n / d$, so there is an even number of divisors. If $n$ is a square, all pairs are pairs of distinct divisors, except for the pair $(\sqrt{n}, \sqrt{n})$. This results in an odd number of divisors. Therefore, $n$ is indeed a square.

## Bézout's Theorem

The concept of common divisors and greatest common divisor (GCD) allows us to define the notion of coprime integers.

Definition 17 (Coprime Numbers).

Let $a, b \in \mathbb{Z}$ and $a_{1}, \ldots, a_{n} \in \mathbb{Z}$. We say that

1. $a$ and $b$ are coprime when $a \wedge b=1$, in other words, there is no non-trivial common divisor of $a$ and $b$.
2. $a_{1}, \ldots, a_{n}$ are coprime in their set when $a_{1} \wedge \cdots \wedge a_{n}=1$.
3. $a_{1}, \ldots, a_{n}$ are pairwise coprime when for all $i, j \in\{1, \ldots, n\}, a_{i} \wedge a_{j}=1$.

## Remark 18.

The only integer that is coprime with itself is 1.

When dealing with more than two numbers, it is important not to confuse the two notions of being pairwise coprime and coprime in their set. In general, we have:

Proposition 19 (Pairwise Coprime $\Rightarrow$ Coprime in Their Set). Let $a_{1}, \ldots, a_{n} \in \mathbb{Z}$. If they are pairwise coprime, then they are coprime in their set.

Proof. Suppose $a_{1}, \ldots, a_{n}$ are pairwise coprime. Then the GCD $d$ of $a_{1} \wedge \cdots \wedge a_{n}$ is a number that divides $a_{1}, \ldots, a_{n-1}$ and $a_{n}$. In particular, $d$ divides $a_{1}$ and $a_{2}$, so it divides $a_{1} \wedge a_{2}=1$. Since the only positive divisor of 1 is 1, $d=1$.

Note, the converse is generally false.

Example 20 (Counterexample).

The numbers 6, 10, and 15 are coprime in their set, but not pairwise coprime.

Remark 21 (Constructing Coprime Integers).

Let $a, b \in \mathbb{Z}^{*}$ and $d=a \wedge b$. We can then write $a=d k$ and $b=d l$ with $k, l \in \mathbb{Z}$. The integers $k$ and $l$ are then coprime. Indeed, if $d^{\prime}>0$ is a common divisor of $k$ and $l$, then $d d^{\prime}$ is a common divisor of $a$ and $b$. But $d$ is the GCD of $a$ and $b$, so $d d^{\prime} \mid d$. This means that $d^{\prime}=1$ and that $k$ and $l$ are coprime.

It can be time-consuming to compute the GCD of two large numbers $a$ and $b$. Fortunately, we can test if they are coprime by looking at their divisors.

## Proposition 22.

Let $a, b, a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{m}$ be coprime.

i $a \wedge b=1 \quad \Leftrightarrow \quad$ For all divisors $d$ of $b, a \wedge d=1$

ii $a \wedge b_{1} \ldots b_{m}=1 \quad \Leftrightarrow \quad \forall j, \quad a \wedge b_{j}=1$

iii $a_{1} \ldots a_{n} \wedge b_{1} \ldots b_{m}=1 \quad \Leftrightarrow \quad \forall i, j, \quad a_{i} \wedge b_{j}=1$

## Remark 23.

1. When decomposing $a$ and $b$ into products of factors $a_{1} \ldots a_{n}$ and $b_{1} \ldots b_{m}$, it is necessary to test all pairs of factors $\left(a_{i}, b_{j}\right):\left(a_{1}, b_{1}\right),\left(a_{1}, b_{2}\right), \ldots,\left(a_{1}, b_{m}\right), \ldots,\left(a_{n}, b_{1}\right), \ldots,\left(a_{n}, b_{m}\right)$.
2. Property 22 gives the following result: the product of numbers coprime with $a$ is still a number coprime with $a$.

The notion of coprime integers is fundamental in number theory. It is the basis of the following theorem, which is a very useful equivalence.

Theorem 24 (Bézout's Theorem).

Let $a, b \in \mathbb{Z}$. Then $a \wedge b=1$ if and only if there exist $u, v \in \mathbb{Z}$ such that

$$
a u+b v=1
$$

Such a pair of integers $(u, v)$ is sometimes called a Bézout pair for $a$ and $b$, and the equation $a u+b v=1$ a Bézout relation.

Corollary 25 (Corollary of Bézout's Theorem).

Let $a, b \in \mathbb{Z}$. Then there exist integers $u, v \in \mathbb{Z}$ such that

$$
a \wedge b=a u+b v
$$

Proof (Corollary). 25 We write $d=a \wedge b$ and $a=d k, b=d l$. We have seen that $k \wedge l=1$. According to Bézout's Theorem, there then exists a Bézout pair $(u, v)$ such that $k u+l v=1$. We multiply everything by $d$ to obtain

$$
d=d k u+d l v=a u+b v
$$

Remark 26 (On Bézout's Theorem).

1. If $(u, v)$ is a Bézout pair for $a$ and $b$ that are coprime, then $(a, b)$ is a Bézout pair for $u$ and $v$, which ensures that $u \wedge v=1$ as well.
2. Any quantity of the form $a u+b v$ is a multiple of the GCD of $a$ and $b$. Theorem 24 (rather its corollary 25) states that $a \wedge b$ is exactly the smallest positive integer of this form.
3. Corollary 25 is not an equivalence, unlike Theorem 24.

Proof (Bézout's Theorem). 24 The theorem is an equivalence between the two statements

i $a \wedge b=1$

ii There exist $u, v \in \mathbb{Z}$ such that $a u+b v=1$

There are thus two implications to prove:

(ii) $\Rightarrow(i)$: We have seen that the GCD of $a$ and $b$ divides any quantity of the form $a u+b v$ with $u, v \in \mathbb{Z}$. Therefore, if $a$ and $b$ admit a Bézout relation, their GCD divides 1, which implies that it is 1.

(i) $\Rightarrow$ (ii): This direction is more difficult to establish. The proof uses a variant of the Euclidean algorithm, the extended Euclidean algorithm.

a We assume $0 \leqslant a \leqslant b$ and set $a_{0}=b$ and $a_{1}=a$ as in the Euclidean algorithm. $a_{0}$ and $a_{1}$ can thus be written in the form $a u+b v$.

b At step $n \in \mathbb{N}^{*}$, we assume that we have constructed the numbers $a_{n-1}=a u_{n-1}+b v_{n-1}$ and $a_{n}=a u_{n}+b v_{n}$ with integers $u_{n_{1}}, v_{n_{1}}, u_{n}, v_{n}$, and that $a_{n-1} \geqslant a_{n}$. We write the Euclidean division of $a_{n-1}$ by $a_{n}$:

$$
a_{n-1}=q a_{n}+a_{n}
$$

with $r<a_{n}$. We expand the $a_{i}$ and rearrange the terms to obtain

$$
\left(u_{n-1}-q u_{n}\right) a+\left(v_{n-1}-q v_{n}\right) b=a_{n+1}
$$

So that $a_{n+1}$ can still be written in the form $a_{n+1}=a u_{n+1}+b v_{n+1}$ with $u_{n+1}=u_{n-1}-q u_{n}$ and $v_{n+1}=v_{n-1}-q v_{n}$. In particular, at step $N$ where the algorithm stops, $a_{N}=a \wedge b=1$ can be written as $1=a_{N}=a u_{N}+b v_{N}$, which is a Bézout relation.