 # MAT 112 Integers and Modern Applications for the Uninitiated

## Section4.4Bé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.

### Example4.26.Bézout’s identity for $$\gcd(28,12)$$.

We find values for $$s$$ and $$t$$ from Theorem 4.25 for $$a := 28$$ and $$b :=12\text{.}$$
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*}

### Problem4.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.

### Checkpoint4.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.
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.

### Problem4.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.
1. $$\displaystyle 63 \fmod 14 = 7$$
2. $$\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.

### Checkpoint4.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.