Extended Euclidean algorithm and modular inverse, step by step

Euclid's algorithm is one of the oldest algorithms still in everyday use: it computes the greatest common divisor of two numbers without having to factor them. Its extended version does something even more useful: it finds the inverse of a number in modular arithmetic, an operation that is essential in cryptography, in error-correcting codes and in solving systems of congruences.

Greatest common divisor

The greatest common divisor gcd(a, b) is the largest integer that divides both a and b. Two numbers whose gcd is 1 are called coprime.

Factoring both numbers and taking the common factors only works with small numbers, because factoring is hard. Euclid's algorithm avoids factoring altogether.

Euclid's algorithm

It rests on a simple observation: if a = q · b + r, then the common divisors of a and b are exactly the common divisors of b and r. Therefore

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

and you repeat until the remainder is zero. The last non-zero remainder is the gcd.

Example: gcd(252, 198).

gcd(252, 198) = 18.

In code:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

The algorithm is extremely fast: the number of steps is at most about five times the number of decimal digits of the smaller number (Lamé's theorem).

Bézout's identity

A fundamental result: for every pair of integers a and b there are integers x and y such that

a · x + b · y = gcd(a, b)

For the previous example: 252 · 4 + 198 · (−5) = 1008 − 990 = 18.

The coefficients x and y can be found by retracing the algorithm's divisions backwards, as we will see shortly with the modular inverse.

The extended algorithm

The extended Euclidean algorithm computes x and y during the descent itself, updating two pairs of coefficients:

def extended_euclid(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b:
        q = a // b
        a, b = b, a - q * b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0   # gcd, x, y with a*x + b*y = gcd

extended_euclid(252, 198)   # (18, 4, -5)

The modular inverse

The inverse of a modulo n is a number b such that a · b ≡ 1 (mod n). It exists if and only if gcd(a, n) = 1.

The link with Bézout is immediate: if gcd(a, n) = 1, then a · x + n · y = 1 for some x and y. Reducing modulo n, the term n · y vanishes and a · x ≡ 1 (mod n) remains. So x is the inverse of a.

Example: the inverse of 7 modulo 40.

• 40 = 5 · 7 + 5
• 7 = 1 · 5 + 2
• 5 = 2 · 2 + 1

Working back: 1 = 5 − 2 · 2 = 5 − 2 · (7 − 5) = 3 · 5 − 2 · 7 = 3 · (40 − 5 · 7) − 2 · 7 = 3 · 40 − 17 · 7.

So 7 · (−17) ≡ 1 (mod 40), and −17 ≡ 23. Check: 7 · 23 = 161 = 4 · 40 + 1.

In Python, since version 3.8, pow(7, -1, 40) returns 23 directly.

The Chinese remainder theorem

A classic problem from ancient Chinese mathematics asks for a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5 and remainder 2 when divided by 7. The Chinese remainder theorem states that, if the moduli are pairwise coprime, a system of this kind always has a solution, unique modulo the product of the moduli (here 105).

The construction uses modular inverses. Let N = 105. For each modulus nᵢ compute Nᵢ = N / nᵢ and its inverse modulo nᵢ:

x = 2 · 35 · 2 + 3 · 21 · 1 + 2 · 15 · 1 = 140 + 63 + 30 = 233 ≡ 23 (mod 105).

The smallest solution is 23. The theorem lets you split calculations with a large modulus into independent calculations with small moduli, and it is used to speed up private-key cryptographic operations.

In short

• Euclid's algorithm computes the gcd by repeated division, without factoring.
• The number of steps grows with the number of digits, not with the size of the numbers.
• Bézout's identity writes the gcd as a combination a · x + b · y.
• If gcd(a, n) = 1, the Bézout coefficient x is the inverse of a modulo n.
• The Chinese remainder theorem combines solutions modulo coprime numbers into a single solution.