1.9: Bezout's Lemma

In Definition 1.4.5 we defined a linear combination of two integers \(a\) and \(b\) to an integer of the form \(as+bt\). If we keep track of the linear combinations of two integers like \(9\) and \(24\), what do we see?

Evaluating \(9s+24t\) for various choices of integers \(s\) and \(t\), and keeping track of the results, shows that the numbers between \(0\) and \(20\) that are linear combinations of \(9\) and \(24\) are the following: \[0, 3, 6, 9, 12, 15, 18.\nonumber \]

One way to begin to convince yourself of this might be to notice that \(3=9(-5) + 24(2)\), and then multiply both sides of this equation by integers to get the following: \[\begin{aligned} 0 &= 9(0) + 24(0);\\ 3 &= 9(-5) + 24(2);\\ 6 &= 9(-10) + 24(4);\\ 9 &= 9(-15) + 24(6);\\ 12 &= 9(-20) + 24(8);\\ 15 &= 9(-25) + 24(10);\\ 18 &= 9(-30) + 24(12).\\\end{aligned}\] Continuing in this way will show you that every multiple of 3 is a linear combination of \(9\) and \(24\). (Can you see why things that are not multiples of 3 are not linear combinations of 9 and 24?)

Doing similar work for other pairs of 9 and another number, we might see that

• every multiples of 9 are the linear combinations of 0 and 9;
• every integer is a linear combination of 1 and 9;
• every integer is a linear combination of 2 and 9;
• the multiples of 3 are the linear combinations of 3 and 9;
• every integer is a linear combination of 4 and 9;
• every integer is a linear combination of 5 and 9;
• the multiples of 3 are the linear combinations of 6 and 9;
• every integer is a linear combination of 7 and 9;
• every integer is a linear combination of 8 and 9;
• the multiples of 9 are the linear combinations of 9 and 9.

There are some definite patterns here. First, the linear combinations of \(a\) and \(b\) always seem to be exactly the set of multiples of some positive integer (notice that the set of every integer is exactly the set of multiples of 1).

Next, the number whose multiples form the linear combinations of \(a\) and \(b\) appears to have a special relationships with \(a\) and \(b\)—looking at the examples above, something may stand out to you: the linear combinations of \(a\) and \(9\) turn out to be exactly the

• multiples of 9 if \(a\) is a multiple of 9,
• multiples of 3 if \(a\) is divisible by 3 but not by 9, and
• multiples of 1 if \(a\) is not divisible by 3.

The following important theorem explains what we have noticed. It will also be crucial to the proofs of some very important theorems in the coming chapters.

Lemma \(\PageIndex{1}\): Bezout's Lemma

For all integers \(a\) and \(b\) there exist integers \(s\) and \(t\) such that \[\gcd(a,b)=sa+tb.\nonumber \]

Furthermore, if \(a\) or \(b\) is nonzero, then \(\gcd(a,b)\) is the smallest positive integer that can be written as \(sa + tb\), and the linear combinations of \(a\) and \(b\) are precisely the multiples of \(\gcd(a,b)\).

Proof

If \(a=b=0\) then \(s\) and \(t\) may be anything since \[\gcd(0,0)=0=s\cdot0+t\cdot0.\nonumber \] So we may assume that \(a\ne 0\) or \(b\ne 0\). Let \[J=\{na+mb:n,m\in\mathbb{Z}\}.\nonumber \] Note that \(J\) contains \(a\), \(-a\), \(b\) and \(-b\) since \[\begin{aligned} a &=1\cdot a+0 \cdot b; \\ -a &=(-1)\cdot a+0 \cdot b; \\ b &=0 \cdot a+1 \cdot b; \\ -b &=0 \cdot a+(-1) \cdot b.\end{aligned}\] Since \(a\ne 0\) or \(b\ne 0\) one of the elements \(a\), \(-a\), \(b\), \(-b\) is positive. So we can say that \(J\) contains some positive integers. Let \(S\) denote the set of positive integers in \(J\). That is, \[S=\{na+mb:na+mb>0,\,n,m\in\mathbb{Z}\}.\nonumber \]

By the Well-Ordering Principle for \(\mathbb{N}\), we know that \(S\) contains a smallest positive integer; call this integer \(d\). Let’s show that \(d=\gcd(a,b)\).

First, we show that \(d\) is a common divisor of \(a\) and \(b\). Note that since \(d\in S\) we have \(d=sa+tb\) for some integers, \(s\) and \(t\). Note also that \(d>0\). To show \(d\mid a\) using the Division Algorithm we write \(a=dq+r\) where \(0\le r<d\). Now \[\begin{aligned} r &=a-dq\\ &=a-(sa+tb)q\\ &=(1-sq)a+(-tq)b.\end{aligned}\] Hence \(r\) is a linear combination of \(a\) and \(b\), and \(r\in J\). If \(r>0\) then \(r\in S\). But this cannot be since \(r<d\) and \(d\) is the smallest integer in \(S\). So we must have \(r=0\). That is, \(a=dq\). Hence \(d\mid a\). By a similar argument we can show that \(d\mid b\). Thus, \(d\) is indeed a common divisor of \(a\) and \(b\).

We now show that \(d\) is the greatest common divisor. Let \(e=\gcd(a,b)\). Then \(e\mid a\) and \(e\mid b\), so by Theorem 1.4.1(3), \(e\mid (sa+tb)\), that is, \(e\mid d\). Since \(e\) and \(d\) are positive, by Theorem 1.4.1(10), we have \(e\le d\). On the other hand, since \(d\) is a common divisor of \(a\) and \(b\), we also know that \(e \leq d\). Hence \(d=\gcd(a,b)\).

Now suppose that \(c\) is any linear combination of \(a\) and \(b\). By Theorem 1.4.1(3), we know that \(d \mid c\), so \(c\) is a multiple of \(d\). On the other hand, if \(h\) is any multiple of \(d\), then \(h=dk\) for some integer \(d\), and multiplying both sides of the equation \(d = sa+tb\) by \(k\) yields \[h = dk = (sk)a + (tk)b,\nonumber \] so \(h\) is indeed a linear combination of \(a\) and \(b\). We have thus shown that the linear combinations of \(a\) and \(b\) are precisely the multiples of \(\gcd(a,b)\).

Example \(\PageIndex{1}\)

\(1=\gcd(2,3)\) and we have \(1=(-1)2+1\cdot 3\). Also we have \(1=2\cdot 2+(-1)3\). So the numbers \(s\) and \(t\) in Bezout’s Lemma are not uniquely determined. In fact, as we will see later there are infinitely many choices for \(s\) and \(t\) for each pair \(a,b\).

Remark \(\PageIndex{1}\)

The above proof is an existence theorem. It asserts the existence of \(s\) and \(t\), but does not provide a way to actually find \(s\) and \(t\). Also the proof does not give any clue about how to go about calculating \(s\) and \(t\). We will give two algorithms in the next chapter for finding \(s\) and \(t\).

We end this chapter with the first two of several consequences of Bezout’s Lemma, one about the greatest common divisor and the other about the least common multiple. As in Section 1.7, let \(C(a,b)\) be the set of all common divisors of \(a\) and \(b\).

Corollary \(\PageIndex{1}\)

Every element of \(C(a,b)\) divides \(\gcd(a,b)\).

Proof

If \(c\) is a common divisor of \(a\) and \(b\), then by Theorem 1.4.1(3), \(c\) divides every linear combination of \(a\) and \(b\). By Bezout’s Lemma, \(d\) is a linear combination of \(a\) and \(b\), so \(c \mid d\).

Proposition \(\PageIndex{1}\)

If \(a\) and \(b\) are positive integers, then their least common multiple satisfies \[\operatorname{lcm}(a,b) = \frac{ab}{\gcd(a,b)}.\nonumber \]

Proof

Let \(q = \dfrac{ab}{\gcd(a,b)}\); our goal is show that \(\operatorname{lcm}(a,b)=q\).

Since \(\gcd(a,b)\) is a common divisor of \(a\) and of \(b\), there exist integers \(v\) and \(w\) such that \(a = v\gcd(a,b)\) and \(b=w\gcd(a,b)\). Then \[q = \frac{ab}{\gcd(a,b)}= bv=aw,\nonumber \] which shows that \(q\) is a common multiple of \(a\) and \(b\). Since \(\operatorname{lcm}(a,b)\) is the smallest of the positive common multiples, we have that \(\operatorname{lcm}(a,b) \leq q\).

Since \(\operatorname{lcm}(a,b)\) is a common multiple of \(a\) and \(b\), there exist integers \(j\) and \(k\) such that \[\operatorname{lcm}(a,b)=ja=kb.\nonumber \] By Bezout’s Lemma, there exist integers \(s\) and \(t\) such \[\gcd(a,b) = as+bt.\nonumber \] Multiplying both sides by \(\operatorname{lcm}(a,b)\) and recalling how \(j\), \(k\), and \(q\) are defined, we find \[\begin{aligned} \operatorname{lcm}(a,b)\gcd(a,b) &= as\operatorname{lcm}(a,b) + bt\operatorname{lcm}(a,b)\\ &= as(kb) + bt(ja)\\ &= (sk+tj)ab\\ &= (sk+tj)q\gcd(a,b). \end{aligned}\] Dividing both sides by \(\gcd(a,b)\) yields \(\operatorname{lcm}(a,b) = (sk+tj)q\), so \(q\) divides \(\operatorname{lcm}(a,b)\). This implies that \(q \leq \operatorname{lcm}(a,b)\).

Since \(\operatorname{lcm}(a,b) \leq q\) and \(\operatorname{lcm}(a,b) \geq q\), we conclude that \(\operatorname{lcm}(a,b)=q\), and the proof is complete.

Exercises

Exercise \(\PageIndex{1}\)

By trial and error, find coefficients \(s\) and \(t\) to make the following equations true:

1. \(60s + 35t = \gcd(60,35)\)
2. \(42s + 28t = \gcd(42,28)\)

Exercise \(\PageIndex{2}\)

Find three different pairs of integers \(s,t\) that all make the equation \(3s + 11t = 1\).

Exercise \(\PageIndex{3}\)

1. True or false, and why? If \(s\) and \(t\) are integers and \(3s + 11t = 1\), then \(\gcd(s,t)=1\).
2. If \(s=9\) and \(t=-24\) and \(19s + 7t = 3\), does this mean that \(\gcd(19,7)=3\)? Whether the answer is yes or no, explain what Bezout’s Lemma says about the integers 19 and 7.

Exercise \(\PageIndex{4}\)

Using Proposition \(\PageIndex{1}\), compute the following.

1. \(\operatorname{lcm}(803,154)\)
2. \(\operatorname{lcm}(11,123)\)
3. \(\operatorname{lcm}(2185,3059)\)

Exercise \(\PageIndex{5}\)

According to the Summer 2017 issue of QuadAngles, a publication of the University of Rhode Island Alumni Association, knowing your least common multiples and greatest common divisors could help you get into college in the University’s early days:

Here are the requirements for admission to the Rhode Island College of Agriculture and Mechanic Arts for September 1893. The College had opened the year before; this is the earliest admission test we could find.

ARITHMETIC

1. Find the L. C. M. and G. C. D. of 724 and 896. ...

Find the answers to this question.

Exercise \(\PageIndex{6}\)

Let \(a>b>0\). Show that if \(a=bq+r\), then \[\operatorname{lcm}(a,b)=\frac{a}{r}\operatorname{lcm}(b,r).\nonumber\] (Hint: Recall Lemma 1.8.2.)