## Section4.4Bézout's Identity

The following theorem follows from the Euclidean Algorithm (Algorithm 4.3.2) and Theorem 3.2.16.

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 $$a$$ and $$b\text{,}$$ we would use repeated substitutions on the results of the Euclidean Algorithm (Algorithm 4.3.2). 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.4.1. In this course we limit our computations to this case. We demonstrate this in the following examples.

We find values for $$s$$ and $$t$$ from Theorem 4.4.1 for $$a := 28$$ and $$b :=12\text{.}$$

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 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*}

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.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.2. 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.4.4 work through a similar example.

Follow these step to compute the greatest common divisor of $$a:=780$$ and $$b:=96$$ and the integers $$s$$ and $$t$$ such that $$(s\cdot a)+(t\cdot b) =\gcd(a,b)\text{.}$$

First we compute $$\gcd(a,b)\text{.}$$ 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) =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{.}$$

$$96$$

$$12$$

$$8$$

$$12$$

$$0$$

$$12$$

$$780$$

$$96$$

$$8$$

$$12$$

$$12$$

$$780$$

$$-8$$

$$96$$

$$1$$

$$-8$$

The pattern observed in the solution of the problem and Checkpoint 4.4.4 can be generalized. We obtain the following theorem.

The condition $$\gcd(a,b)=a \fmod b$$ in Theorem 4.4.5 means that in the Euclidean algorithm the instructions in the repeat until loop are only executed twice.

We apply Theorem 4.4.5 in the solution of a problem.

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.4.5. 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.4.5 in the solution of Checkpoint 4.4.7.

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{.}$$

$$1$$
$$1$$
$$-3$$