Theorem 4.25. 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 following theorem follows from the Euclidean Algorithm (Algorithm 4.17) and Theorem 3.20.
The values \(s\) and \(t\) from Theorem 4.25 are called the cofactors of \(a\) and \(b\text{.}\) To find \(s\) and \(t\) for any \(a\) and \(b\text{,}\) we would use repeated substitutions on the results of the Euclidean Algorithm (Algorithm 4.17). This works because the algorithm connects \(a\) and \(b\) to the \(\gcd(a,b)\) by a series of related equations.
When \(\gcd(a, b) = a \fmod b\text{,}\) we can easily find the values of \(s\) and \(t\) from Theorem 4.25. In this course we limit our computations to this case. We demonstrate this in the following examples.
Example 4.26. Bézout’s identity for \(\gcd(28,12)\).
First, we compute the \(\gcd(28, 12)\) using the Euclidean Algorithm (Algorithm 4.17). 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*}
So \(s = 1\) and \(t = -2\text{.}\)
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.27. Bézout’s identity for \(\gcd(5,2)\).
Find integers \(s\) and \(t\) such that \(s\cdot5+t\cdot2=\gcd(5,2)\text{.}\)
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.17) 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.26. 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 read of the values \(s:=1\) and \(t:=-2\text{.}\) Note that \(t=-(5 \fdiv 2)\text{.}\)
In Checkpoint 4.28 work through a similar example.
Checkpoint 4.28. Find the cofactors.
Let \(a:=780\) and \(b:=96\text{.}\)
Follow these step to compute the greatest common divisor of \(a\) and \(b\) and the integers \(s\) and \(t\) such that \((s\cdot a)+(t\cdot b) =\gcd(a,b)\text{.}\)
First we compute \(\gcd(a,b)\) using the Euclidean algorithm.
In addition to the remainder we also compute the quotient.
Let \(a_1:=b=\) and let \(b_1:= a \bmod b =\) and let \(q_1:= a \mbox{ div } b=\)
Let \(a_2:=b_1\)= and let \(b_2:= a_1 \bmod b_1 =\)
We have computed \(\gcd(780,96) =a_2=b_1=\).
Now write \(a=(b\cdot q_1)+b_1\text{:}\)
\(=\Bigl(\) \(\cdot\)\(\Bigr)+\)
Rearranging the values, write \(b_1= (1\cdot a)+((-q_1)\cdot b)\) :
\(=\Bigl(1\cdot\) \(\Bigr)+\Bigl(\)\(\cdot\)\(\Bigr)\)
Read off the values of \(s\) and \(t\text{.}\) Recall that \(b_1=\gcd(a,b)\text{.}\)
With \(s=\) and \(t=\) we have \(\gcd(a,b)=(s\cdot a)+(t\cdot b)\text{.}\)
The pattern observed in the solution of the problem and Checkpoint 4.28 can be generalized. We obtain the following theorem.
Theorem 4.29.
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.29 means that in the Euclidean algorithm the instructions in the repeat until loop are only executed twice.
We apply Theorem 4.29 in the solution of a problem.
Problem 4.30. 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.29. 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*}
Apply Theorem 4.29 in the solution of Checkpoint 4.31.
Checkpoint 4.31. Find the cofactors.
Compute the greatest common divisor of \(a:=10\) and \(b:=3\) and the integers \(s\) and \(t\) such that \((s\cdot a)+(t\cdot b) =\gcd(a,b)\text{.}\)
We have \(\gcd(10,3)=\). Now find the numbers \(s\) and \(t\) whose existence is guaranteed by Bezout’s identity.
With \(s=\) and \(t=\) we have \((s\cdot a)+(t\cdot b) =\gcd(a,b)\text{.}\)
In the video in Figure 4.32 we summarize the results from above and give some additional examples.
