Extended Euclidean Algorithm

The Extended Euclidean Algorithm not only finds the GCD but also expresses it as a linear combination of the two numbers. This is critical for finding modular inverses.

Bézout Coefficients

For any integers

a, b

, there exist integers

x, y

such that:

a x + b y = g cd (a, b)

The Algorithm (Back-Substitution)

Run the standard Euclidean Algorithm, saving the equations. Then work backwards.

Example (Find x, y for 252x + 105y = 21)

Forward:

$252 = 2 (105) + 42 ⟹ 42 = 252 - 2 (105)$
$105 = 2 (42) + 21 ⟹ 21 = 105 - 2 (42)$

Backward: Start with the GCD equation (2):

21 = 105 - 2 (42)

Substitute for 42 using equation (1):

21 = 105 - 2 (252 - 2 (105))

21 = 105 - 2 (252) + 4 (105)

21 = 5 (105) - 2 (252)

Solution:

x = - 2, y = 5

Table Method

A systematic way to track coefficients

x_{i}, y_{i}

such that

r_{i} = a x_{i} + b y_{i}

at every step.

Practice Problems

Exercise (Problem 1)

Find integers

x, y

such that

37 x + 10 y = 1

Exercise (Problem 2)

Express

g cd (119, 204)

as a linear combination of 119 and 204.

Exercise (Problem 3)

Solve the Diophantine equation

12 x + 18 y = 30