Theorem 4.20. Bézout’s identity.
For all natural numbers \(a\) and \(b\) there exist integers \(s\) and \(t\) with \((s\cdot a)+(t\cdot b)=\gcd(a,b)\text{.}\)
Section 4.4 Bézout’s Identity
The values \(s\) and \(t\) from Theorem 4.20 are called the cofactors of \(a\) and \(b\text{.}\) To find \(s\) and \(t\) for any given \(a\) and \(b\text{,}\) one uses repeated substitutions on the results of the Euclidean Algorithm 4.14. This works because the algorithm connects \(a\) and \(b\) to the \(\gcd(a,b)\) by a series of related equations.
In the problems in this course we only consider Bézout’s Identity the special case covered by the following theorem.
Theorem 4.21.
Let \(a\) and \(b\) be natural numbers. If \(\gcd(a,b)=a \fmod b\) then \(s\cdot a+t\cdot b=\gcd(a,b)\) for \(s=1\) and \(t=-(a\fdiv b)\text{.}\)
The condition \(\gcd(a,b)=a \fmod b\) in Theorem 4.21 means that in the Euclidean algorithm the instructions in the repeat until loop are only executed twice.
We illustrate why this works in the following two examples. Applying the theorem is even easiers as you can see in Theorem 4.21.
Example 4.22. Bézout’s identity for \(\gcd(28,12)\).
First, we compute the \(\gcd(28, 12)\) using the Euclidean Algorithm (Algorithm 4.14). In the table we give the values of the variables at the end of step (1) in each iteration of the loop.
| step | \(r\) | \(a\) | \(b\) |
|---|---|---|---|
| Input | \(28\) | \(12\) | |
| (1) | \(28\fmod 12=4\) | \(12\) | \(4\) |
| (1) | \(12\fmod 4=0\) | \(1\) | \(0\) |
| Output | 4 |
So the \(\gcd(28, 12) = 28 \fmod 12 = 4\text{.}\) To find \(s\) and \(t\) with \((s\cdot 28)+(t\cdot 12)=\gcd(28,12)=4\) we need
-
the remainder from the first iteration of the loop \(r:=a\fmod b = 28\fmod 12=4\) and
-
the quotient \(q := a\fdiv b = 28 \fdiv 12 = 2\text{.}\)
Now we can write \(a\) in the form \(a = b\cdot q + r\text{:}\)
\begin{equation*}
28 = 12 \cdot 2 + 4
\end{equation*}
We write \(a = (b\cdot q) + r\) in slightly more complicated way, namely as \((1 \cdot a) = (q \cdot b) + r\text{.}\) Solving \((1\cdot a) = (q\cdot b) + r\) for \(r\) we get \((1 \cdot a) - (q \cdot b) = r\text{.}\) To bring this into the desired form \((s\cdot a)+(t\cdot b)=\gcd(a,b)\) we write \(- (q \cdot b)\) as \(+ ((-q) \cdot b)\) and obtain
\begin{equation*}
(1 \cdot a) + ((-q) \cdot b) = r
\end{equation*}
Plugging in our values for \(a\text{,}\) \(b\text{,}\) \(q\text{,}\) and \(r\) we obtain
\begin{equation*}
(1 \cdot 28) + ((-2)\cdot 12) = 4
\end{equation*}
The cofactors \(s\) and \(t\) are not unique. Using the numbers from this example, the values \(s=-5\) and \(t=12\) would also have been a solution since then
\begin{equation*}
(s\cdot 28)+(t\cdot 12)
(-5\cdot 28)+(12\cdot 12)
=-140 +144=4.
\end{equation*}
Problem 4.23. Bézout’s identity for \(\gcd(5,2)\).
Solution.
Although it is easy to see that the greatest common divisor of 5 and 2 is 1, we need some of the intermediate result from the Euclidean algorithm to find \(s\) and \(t\text{.}\) Following the Euclidean algorithm (Algorithm 4.14) for the input values \(a:=5\) and \(b:=2\) we get:
| step | \(r\) | \(a\) | \(b\) |
|---|---|---|---|
| Input | \(5\) | \(2\) | |
| (1) | \(5\fmod 2=1\) | \(2\) | \(1\) |
| (1) | \(2\fmod 1=0\) | \(1\) | \(0\) |
| Output | 1 |
We have confirmed that \(\gcd(5,2)=1\text{.}\) Since the Euclidean algorithm terminated after 2 iterations we can use the same trick as in Example 4.22. We get
\begin{equation*}
r := 5 \fmod 2 = 1
\end{equation*}
and
\begin{equation*}
q := 5 \fdiv 2 = 2
\end{equation*}
Plugging these into the formula
\begin{equation*}
(1 \cdot a) + ((-q) \cdot b) = r
\end{equation*}
we get
\begin{equation*}
(1 \cdot 5) + ((-2) \cdot 2) = 1\text{.}
\end{equation*}
We apply Theorem 4.21 in the solution of a problem.
Problem 4.24. Find \(s\) and \(t\) such that \(s\cdot 63+t\cdot 14=\gcd(63,14)\).
For \(a=63\) and \(b=14\) find integers \(s\) and \(t\) such that \(s\cdot a+t\cdot b=\gcd(a,b)\text{.}\)
Solution.
We find the greatest common divisor of 63 and 14 using the Euclidean Algorithm.
-
\(\displaystyle 63 \fmod 14 = 7\)
-
\(\displaystyle 14 \fmod 7 = 0\)
So the Euclidean Algorithm ends after running through the loop twice and returns \(\gcd(63,14)=7\text{.}\) By Theorem 4.21. we have \(s=1\) and \(t=-(63 \fdiv 14) = -4\text{.}\)
We check whether the result is correct:
\begin{equation*}
1\cdot 63+(-4)\cdot 14=63+(-56)=7\text{.}
\end{equation*}
In the video in Figure 4.25 we summarize the results from above and give some additional examples.
