18.3 Extended Euclidean Algorithm

The Euclidean Algorithm computes the greatest common divisor of two integers. In many applications, however, the GCD alone is not enough. We often need to know how the GCD can be expressed as a linear combination of the original numbers.

Given integers a and b, we want to find integers x and y such that:

ax + by = gcd(a,b)

This problem appears throughout number theory, cryptography, modular arithmetic, coding theory, and algorithm design.

The Extended Euclidean Algorithm solves it efficiently while computing the GCD itself.

Problem

Given integers:

a
b

find:

g = gcd(a,b)

and integers:

x
y

such that:

ax + by = g

Example:

a = 30
b = 18

The GCD is:

gcd(30,18) = 6

One solution is:

x = -1
y = 2

because:

30(-1) + 18(2)
=
-30 + 36
=
6

Bézout's Identity

The Extended Euclidean Algorithm is based on a fundamental theorem.

Bézout's Identity

For any integers a and b:

gcd(a,b)

can always be written as:

ax + by

for some integers x and y.

Examples:

gcd(15,10)=5

15(1)+10(-1)=5

and:

gcd(35,12)=1

35(-1)+12(3)=1

The theorem guarantees existence.

The algorithm finds the coefficients.

From Euclid to Extended Euclid

Recall the Euclidean recursion:

gcd(a,b)
=
gcd(b,a mod b)

Suppose we recursively solve:

bx₁ + (a mod b)y₁ = g

Since:

a mod b = a - ⌊a/b⌋b

substituting gives:

bx₁ + (a - ⌊a/b⌋b)y₁ = g

Expanding:

ay₁ + b(x₁ - ⌊a/b⌋y₁) = g

Therefore:

x = y₁
y = x₁ - ⌊a/b⌋y₁

The recursive solution can reconstruct coefficients for the larger problem.

This observation produces the entire algorithm.

Recursive Algorithm

Base case:

gcd(a,0)=a

and:

a·1 + 0·0 = a

Therefore:

x = 1
y = 0

Recursive case:

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0

    g, x1, y1 = extended_gcd(b, a % b)

    x = y1
    y = x1 - (a // b) * y1

    return g, x, y

Example Walkthrough

Compute:

gcd(30,18)

Euclidean steps:

30 = 18×1 + 12
18 = 12×1 + 6
12 = 6×2 + 0

Thus:

g = 6

Now back-substitute.

From:

6 = 18 - 12

and:

12 = 30 - 18

Substitute:

6
=
18 - (30 - 18)

Simplify:

6
=
2×18 - 30

Therefore:

6
=
30(-1) + 18(2)

Hence:

x = -1
y = 2

Verification:

30(-1)+18(2)=6

Correct.

Trace Example

Consider:

extended_gcd(35,12)

Euclidean reductions:

35 = 12×2 + 11
12 = 11×1 + 1
11 = 1×11 + 0

GCD:

Back-substitution:

1 = 12 - 11

and:

11 = 35 - 12×2

Substitute:

1
=
12 - (35 - 12×2)

1
=
3×12 - 35

Thus:

1
=
35(-1) + 12(3)

Result:

x = -1
y = 3

Iterative Version

The recursive form is elegant, but iterative implementations are common.

def extended_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1

    while r != 0:
        q = old_r // r

        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t

    return old_r, old_s, old_t

At termination:

old_r = gcd(a,b)
old_s = x
old_t = y

This version uses constant memory and avoids recursion.

Solving Linear Diophantine Equations

Consider:

ax + by = c

A solution exists exactly when:

gcd(a,b) | c

Example:

15x + 25y = 10

Since:

gcd(15,25)=5

and:

5 | 10

solutions exist.

First compute:

15(2)+25(-1)=5

Multiply by:

10/5 = 2

Result:

15(4)+25(-2)=10

One valid solution is:

x=4
y=-2

The Extended Euclidean Algorithm provides the starting point for all such equations.

Modular Inverse

One of the most important applications is modular inversion.

Given:

and modulus:

find:

a⁻¹ mod m

such that:

a·a⁻¹ ≡ 1 (mod m)

The inverse exists only when:

gcd(a,m)=1

Suppose:

7x + 26y = 1

Extended Euclid finds:

x = 15
y = -4

Therefore:

7×15 ≡ 1 (mod 26)

The inverse is:

Verification:

105 mod 26 = 1

Correct.

Example: Computing an Inverse

Find:

3⁻¹ mod 11

Run Extended Euclid:

11 = 3×3 + 2
3 = 2×1 + 1
2 = 1×2 + 0

Back-substitute:

1 = 3 - 2

2 = 11 - 3×3

Therefore:

1
=
3 - (11 - 3×3)

1
=
4×3 - 11

Thus:

3×4 ≡ 1 (mod 11)

The inverse is:

Verification:

12 mod 11 = 1

Complexity Analysis

The Extended Euclidean Algorithm performs the same sequence of remainder reductions as the Euclidean Algorithm.

Time complexity:

O(log(min(a,b)))

Space complexity:

O(log(min(a,b)))

for the recursive version.

Iterative version:

O(1)

extra space.

The coefficient reconstruction adds only constant work per step.

Applications

Modular Arithmetic

Computing inverses:

a⁻¹ mod m

RSA Cryptography

Private key generation uses modular inverses.

Chinese Remainder Theorem

Reconstruction coefficients are computed with Extended Euclid.

Rational Arithmetic

Fraction normalization often uses Bézout coefficients.

Diophantine Equations

Integer solutions begin with Extended Euclid.

Computational Geometry

Lattice and grid algorithms frequently require Bézout coefficients.

Common Mistakes

Ignoring Negative Coefficients

The coefficients often become negative.

Example:

30(-1)+18(2)=6

Negative values are completely valid.

Assuming an Inverse Always Exists

An inverse exists only when:

gcd(a,m)=1

Example:

2 mod 8

has no inverse because:

gcd(2,8)=2

Returning the Wrong Coefficient

Many implementations compute correct coefficients but return them in the wrong order.

Always verify:

ax + by = gcd(a,b)

before using the result.

Takeaway

The Extended Euclidean Algorithm extends the Euclidean Algorithm by computing integers x and y satisfying Bézout's identity:

ax + by = gcd(a,b)

while retaining logarithmic complexity. These coefficients unlock several of the most important tools in computational number theory, including modular inverses, linear Diophantine equations, the Chinese Remainder Theorem, and public-key cryptography. The algorithm serves as one of the central building blocks for everything that follows in modular arithmetic and advanced number-theoretic computation.