Theorem 4.4.1. 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.4.1 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.3.2. This works because the algorithm connects \(a\) and \(b\) to the \(\gcd(a,b)\) by a series of related equations.
In this course, we use only the special case of Bézout’s Identity given by the next theorem.
Theorem 4.4.2.
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.4.2 means that the repeat until loop in the Euclidean algorithm runs only twice.
The next two examples show why this works. The theorem in Theorem 4.4.2 gives an even easier method.
Example 4.4.3. Bézout’s identity for \(\gcd(28,12)\).
First, we compute the \(\gcd(28, 12)\) using the Euclidean Algorithm (Algorithm 4.3.2). 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 get
\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.4.4. 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.3.2) 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.4.3. 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.4.2 in the solution of a problem.
Problem 4.4.5. 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.4.2. 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.4.6 we summarize the results from above and give some more examples.
