Bézout’s Identity

Section 4.4 Bézout’s Identity

The following theorem follows from the Euclidean Algorithm (Algorithm 4.17) and Theorem 3.20.

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) .

🔗

The values

s

and

t

from Theorem 4.25 are called the cofactors of

a

and

b .

To find

s

and

t

for any

a

and

b,

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 mod b,

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)$ .

🔗

We find values for

s

and

t

from Theorem 4.25 for

a := 28

and

b := 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 mod 12 = 4$	$12$	$4$
(1)	$12 mod 4 = 0$	$1$	$0$
Output		4

🔗

So the

gcd (28, 12) = 28 mod 12 = 4 .

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 mod b = 28 mod 12 = 4$ and
the quotient $q := a div b = 28 div 12 = 2 .$

🔗

Now we can write

a

in the form

a = b \cdot q + r :

28 = 12 \cdot 2 + 4

🔗

We write

a = (b \cdot q) + r

in slightly more complicated way, namely as

(1 \cdot a) = (q \cdot b) + r .

Solving

(1 \cdot a) = (q \cdot b) + r

for

r

we get

(1 \cdot a) - (q \cdot b) = r .

To bring this into the desired form

(s \cdot a) + (t \cdot b) = gcd (a, b)

we write

- (q \cdot b)

+ ((- q) \cdot b)

and obtain

(1 \cdot a) + ((- q) \cdot b) = r

🔗

Plugging in our values for

a,

b,

q,

and

r

we obtain

(1 \cdot 28) + ((- 2) \cdot 12) = 4

🔗

s = 1

and

t = - 2 .

🔗

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

(s \cdot 28) + (t \cdot 12) (- 5 \cdot 28) + (12 \cdot 12) = - 140 + 144 = 4.

🔗

Problem 4.27. Bézout’s identity for $gcd (5, 2)$ .

🔗

Find integers

s

and

t

such that

s \cdot 5 + t \cdot 2 = 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 .

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 mod 2 = 1$	$2$	$1$
(1)	$2 mod 1 = 0$	$1$	$0$
Output		1

We have confirmed that

gcd (5, 2) = 1 .

Since the Euclidean algorithm terminated after 2 iterations we can use the same trick as in Example 4.26. We get

r := 5 mod 2 = 1

and

q := 5 div 2 = 2

Plugging these into the formula

(1 \cdot a) + ((- q) \cdot b) = r

we get

(1 \cdot 5) + ((- 2) \cdot 2) = 1 .

We read of the values

s := 1

and

t := - 2 .

Note that

t = - (5 div 2) .

🔗

In Checkpoint 4.28 work through a similar example.

Checkpoint 4.28. Find the cofactors.

Let

a := 780

and

b := 96 .

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) .

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 mod b =

and let

q_{1} := a div b =

Let

a_{2} := b_{1}

= and let

b_{2} := a_{1} mod b_{1} =

We have computed

gcd (780, 96) = a_{2} = b_{1} =

Now write

a = (b \cdot q_{1}) + b_{1} :

= (

\cdot

) +

Rearranging the values, write

b_{1} = (1 \cdot a) + ((- q_{1}) \cdot b)

= (1 \cdot

) + (

\cdot

)

Read off the values of

s

and

t .

Recall that

b_{1} = gcd (a, b) .

With

s =

and

t =

we have

gcd (a, b) = (s \cdot a) + (t \cdot b) .

🔗

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 mod b

then

s \cdot a + t \cdot b = gcd (a, b)

for

s = 1

and

t = - (a div b) .

🔗

The condition

gcd (a, b) = a mod 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) .

Solution.

We find the greatest common divisor of 63 and 14 using the Euclidean Algorithm.

$63 mod 14 = 7$
$14 mod 7 = 0$

So the Euclidean Algorithm ends after running through the loop twice and returns

gcd (63, 14) = 7 .

By Theorem 4.29. we have

s = 1

and

t = - (63 div 14) = - 4 .

We check whether the result is correct:

1 \cdot 63 + (- 4) \cdot 14 = 63 + (- 56) = 7 .

🔗

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) .

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) .

🔗

In the video in Figure 4.32 we summarize the results from above and give some additional examples.

🔗

Figure 4.32. Bézout’s Identity by Matt Farmer and Stephen Steward

Prev Top Next

Section 4.4 Bézout’s Identity

Theorem 4.25. Bézout’s identity.

Example 4.26. Bézout’s identity for gcd(28,12).

Problem 4.27. Bézout’s identity for gcd(5,2).

Checkpoint 4.28. Find the cofactors.

Theorem 4.29.

Problem 4.30. Find s and t such that s⋅63+t⋅14=gcd(63,14).

Checkpoint 4.31. Find the cofactors.

Example 4.26. Bézout’s identity for $gcd (28, 12)$ .

Problem 4.27. Bézout’s identity for $gcd (5, 2)$ .

Problem 4.30. Find $s$ and $t$ such that $s \cdot 63 + t \cdot 14 = gcd (63, 14)$ .