2.1: Bézout's Lemma

Definition 2.1

The floor of a real number \(\theta\) is defined as follows: \(\lfloor \theta \rfloor\) is the greatest integer less than than or equal to \(\theta\). The fractional part \(\{\theta\}\) of the number \(\theta\) is defined as \(\theta-\lfloor \theta \rfloor\). Similarly, the ceiling of \(\theta\), \(\lceil \theta \rceil\), gives the smallest integer greater than or equal to \(\theta\).

By the well-ordering principle, Corollary 1.8, the number \(\lfloor \theta \rfloor\) and \(\lceil \theta \rceil\) exist for any \(\theta \in \mathbb{R}\).

Definition 2.2

Given a number \(\xi \in \mathbb{R}\), we denote its norm (or absolute value) \(|\xi|\) by \(N(\xi)\).

This last definition seems clumsy and unnecessary in the present context. But it will save us much trouble later on (see Section ??).

Lemma 2.3

Given \(r_{1}\) and \(r_{2}\) with \(r_{2} > 0\), then there are unique \(q_{2}\) and \(r_{3} \ge 0\) with \(N(r_{3}) < N(r_{2})\) such that \(r_{1} = r_{2}q_{2}+r_{3}\).

Proof

Noting that \(\frac{r_{1}}{r_{2}}\) is a rational number, we can choose the integer \(q_{2} = \lfloor \frac{r_{1}}{r_{2}} \rfloor\) so that

\[\frac{r_{1}}{r_{2}} = q_{2}+\epsilon \nonumber\]

where \(\epsilon \in [0, 1)\). The integer \(q_{2}\) is called the quotient. Multiplying by \(r_{2}\) gives the result.

Note that \(r_{3} \in \{0, \cdots, r_{2}-1\}\). Thus among other things, this lemma implies that every integer has a unique residue (see Definition 1.6). If \(N(r_{1}) < N(r_{2})\), then \(q_{2} = 0\). In this case, \(\epsilon = \frac{r_{1}}{r_{2}}\) and we learn nothing new. But if \(N(r_{1}) > N(r_{2})\), then \(q_{2} \ne 0\) and we have written \(r_{1}\) as a multiple of \(r_{2}\) plus a remainder \(r_{3}\).

Definition 2.4

Given \(r_{1}\) and \(r_{2}\) with \(r_{2} > 0\), the computation of \(q_{2}\) and \(r_{3}\) satisfying Lemma 2.3 is called the division algorithm. Note that \(r_{3} = \mbox{Res}_{r_{2}} (r_{1})\).

Theorem 2.5 (Bezout's Lemma)

Let \(a\) and \(b\) be such that \(\gcd (a,b) = d\). Then \(ax+by = c\) has integer solutions for \(x\) and \(y\) if and only if \(c\) is a multiple of \(d\).

Proof

Let \(S\) and \(ν(S)\) be the sets:

\[S = \{ax+by |x, y \in \mathbb{Z}, ax+by \ne 0\} \nonumber\].

\[ν(S) = \{N(s) |s \in S\} \subseteq \mathbb{N} \nonumber\]

Then \(ν(S) \ne 0\) and is bounded from below. Thus by the well-ordering principle of \(\mathbb{N}\), it has a smallest element \(e\). Then there is an element \(d \in S\) that has that norm: \(N(d) = e\).

For that \(d\), we use the division algorithm to establish that there are \(q\) and \(r \ge 0\) such that

\[\begin{array}{ccc} {a = qd+r}&{and}&{N(r) < N(d)} \end{array} \nonumber\]

Now substitute \(d = ax+by\). A short computation shows that \(r\) can be rewritten as:

\[r = a(1-qx)+b(qy) \nonumber\]

This shows that \(r \in S\). But we also know from (2.1) that \(N(r)\) is smaller than \(N(d)\). Unless \(r = 0\), this is a contradiction because of the way \(d\) is defined. But \(r = 0\) implies that \(d\) is a divisor of \(a\). The same argument shows that \(d\) is also a divisor of \(b\). Thus \(d\) is a common divisor of both \(a\) and \(b\).

Now let \(e\) be any divisor of both \(a\) and \(b\). Then \(e | (ax+by)\), and so \(e|d\). But if \(e|d\), then \(N(e)\) must be smaller than or equal to \(N(d)\). Therefore, \(d\) is the greatest common divisor of both \(a\) and \(b\).

By multiplying \(x\) and \(y\) by \(f\), we achieve that for any multiple \(fd\) of \(d\) that

\[afx+bfy = fd \nonumber\]

On the other hand, let \(d\) be as defined above and suppose that \(x, y\), and \(c\) are such that

\[ax+by = c \nonumber\]

Since \(d\) divides \(a\) and \(b\), we must have that \(d|c\), and thus \(c\) must be a multiple of d.