(Set of Bézout pairs)

Let $a, b \in \mathbb{Z}$ and $d=a \wedge b$. Suppose that $(u, v)$ is a pair of integers such that $a u+b v=d$.

1. Let $(x, y)$ be another pair of integers. Find a necessary and sufficient condition on $(x, y)$ for $a x+b y=d$.
2. Deduce the set $E$ of pairs $(x, y)$ satisfying $a x+b y=d$. How many are there?
1. We have seen that suitable pairs are exactly the Bézout pairs for the coprime integers \( k = a / d \) and \( l = b / d \). By replacing \( a \) with \( k \) and \( b \) with \( l \), we can assume they are coprime. We then write

$$
\begin{aligned}
a x + b y = 1 & \Leftrightarrow a x + b y = a u + b v \\
& \Leftrightarrow a(x - u) = b(v - y) \\
& \Rightarrow a \mid b(v - y) \text{ and } b \mid a(x - u) \\
& \Leftrightarrow a \mid (v - y) \text{ and } b \mid (x - u) \quad \text{ by Gauss's lemma } \\
& \Leftrightarrow \exists x', y' \in \mathbb{Z}, \quad y = v - y' a \text{ and } \quad x = u + x' b
\end{aligned} \quad \text{ of }
$$

We see that we are now looking for pairs \((x', y')\) such that \(a(u + x' b) + b(v - y' a) = a u + b v\). But

$$
a(u + x' b) + b(v - y' a) = a u + b v \quad \Leftrightarrow \quad a x' b - b y' a = 0 \quad \Leftrightarrow \quad x' = y'
$$

Thus, we obtain the following necessary and sufficient condition:

$$
a x + b y = d \quad \Leftrightarrow \quad \exists k \in \mathbb{Z}, \quad x = u + k b \quad \text{ and } \quad y = v - k a
$$

2. There are therefore infinitely many suitable pairs, and we can describe the set as follows:

$$
E = \{(u + k b, v - k a) \quad \text{ for all } k \in \mathbb{Z}\}
$$

An immediate consequence of Bézout's theorem 24 is the very useful Gauss's lemma.

Lemma 28 (Gauss's lemma).

Let \( a, b, d \in \mathbb{Z} \). If \( d \mid a b \) and \( a \wedge d = 1 \), then \( d \mid b \).

Proof. Suppose \( d \mid a b \) and \( a \wedge d = 1 \). There exist \( k, u, v \in \mathbb{Z} \) such that \( a u + d v = 1 \) and \( a b = d k \). We multiply this Bézout relation by \( b \), which gives

$$
b = a u b + d v b = d k u + d v b = d(k u + v b)
$$

hence \( d \mid b \).

## LCM and complementarity with the GCD

Just as they can have common divisors, two numbers \( a \) and \( b \) have common multiples. For example, the product \( a b \) is one. But there can be smaller ones: if \( a \mid b \), then \( b \) is a common multiple of \( a \) and \( b \).

Definition 29 (Least Common Multiple).

1. Let \( a, b \in \mathbb{Z} \). The Least Common Multiple (LCM) of \( a \) and \( b \), denoted \( a \vee b \), is the smallest non-zero natural number \( m \) that is a multiple of both \( a \) and \( b \). In the case where \( a \) or \( b \) is zero, we also set by convention \( a \vee b = 0 \).
2. More generally, if \( a_1, \ldots, a_n \in \mathbb{Z} \), their LCM is denoted \( a_1 \vee \cdots \vee a_n \) and defined as the smallest positive non-zero number that is a multiple of each of the \( a_i \).

The LCM has the following properties, generalizable to a family of integers.

Proposition 30 (Properties of the LCM).

Let \( a, b \in \mathbb{Z} \).

i In the non-degenerate case where \( a, b \) are non-zero, we have the inequality

$$
\max (|a|, |b|) \leqslant a \vee b \leqslant |a| \times |b|
$$

ii If \( m \) is a common multiple of \( a \) and \( b \), then \( a \vee b \mid m \).

We see that the GCD and LCM have similar properties, and there is a kind of complementarity between them. This is expressed by the following property.

Proposition 31 (Complementarity of GCD and LCM).

Let \( a, b \in \mathbb{N} \). Then we have the identity

$$
(a \wedge b)(a \vee b) = a b
$$

Proof. Consider first the case where \( a \) and \( b \) are coprime. In this case, the equality simply means that \( a \vee b = a b \). Indeed, since \( m = a \vee b \) is a multiple of \( a \), it can be written as \( m = k a \) for some \( k \in \mathbb{Z} \). But we also have \( b \mid m = k a \). By Gauss's lemma 28, this implies that \( b \mid k \). Thus, we can write \( k = b l \) for some \( l \in \mathbb{Z} \) and \( m = l a b \). Since \( a b \) is already a common multiple of \( a \) and \( b \), \( m = l a b \mid a b \), which implies that \( |l| = 1 \) and thus \( m = a b \).

Next, consider the general case. We write \( d = a \wedge b \) and \( a = d k, b = d l \) for \( k, l \in \mathbb{Z} \) coprime. Since \( d \) divides \( a \) and \( b \), it must also divide any multiple of \( a \) and \( b \) and in particular their LCM. We can therefore write this LCM in the form \( m = d m' \) with \( m' \in \mathbb{N} \). But for any number \( n \in \mathbb{Z} \):

$$
d k = a \mid n d \quad \text{ and } \quad d l = b \mid n d \quad \Leftrightarrow \quad k \mid n \quad \text{ and } \quad l \mid n \quad \Leftrightarrow \quad k l = k \vee l \mid n
$$

Thus, we have \( k l \mid m' \) and \( d k l \mid m \). But since \( d k l \) is a common multiple of \( a \) and \( b \), we also have \( m \mid d k l \) and thus \( m = d k l \). We conclude that we indeed have

$$
a b = d k \times d l = d \times d k l = (a \wedge b) \times (a \vee b)
$$

The complementarity identity between GCD and LCM 31 allows us to compute the LCM of two integers in practice, since we already have a method to compute the GCD.

## Key Points

In conclusion of this first course in number theory, here is the essential information that must be remembered for the rest:

The divisibility relation 7 is an order relation on \(\mathbb{N}\).

All integers are multiples of 1 and divisors of 0.

The only positive divisor (resp. multiple) of 1 (resp. 0) is itself.

Any common divisor is a divisor of the GCD.

Any common multiple is a multiple of the LCM.

## Equivalence in Bézout's theorem 24

The only number that is coprime with itself is 1.

Euclidean algorithm 15: the GCD is "preserved by Euclidean division" ??.

Gauss's lemma 28: we can "eliminate" coprime factors in a divisibility relation.

We have also seen some techniques that are useful in proofs everywhere:

Prove an equality of natural numbers \( a \) and \( b \) by showing that \( a \mid b \) and \( b \mid a \).

Prove that two integers \( a \) and \( b \) are coprime by showing that any common divisor \( d \) of \( a \) and \( b \) is a divisor of 1.

Prove that an algorithm terminates by the principle of infinite descent 16.

And finally some tricks that can simplify the solution of exercises:

Reduce to the case of coprime integers before considering the general case, by dividing by the GCD.

Treat special cases separately, such as 1, 0, coprime numbers, equal numbers. It is important to read the statement carefully to check if the numbers can be negative, zero, strictly positive, etc.

The Euclidean algorithm and its extension are tedious to apply in practice. However, knowing and understanding their functioning well allows you to remember almost all the theorems of the course: Béz