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.
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.
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*}
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
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:
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*}
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{.}\)
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.
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{.}\)