Number Theory · Beginner · 8 min read

The Extended Euclidean Algorithm Explained

The Euclidean algorithm is over two thousand years old and is still one of the most useful procedures in mathematics. Its extended form is the engine behind modular inverses, and therefore behind RSA key generation.

The Euclidean algorithm

The idea is that the common divisors of a and b are exactly the common divisors of b and the remainder of a divided by b. So gcd(a, b) = gcd(b, a mod b). Repeat until the remainder is 0; the last non-zero remainder is the greatest common divisor. The numbers shrink quickly, so even 300-digit numbers need only a few hundred steps.

Going backwards: Bézout's identity

Every remainder in the algorithm is a combination of a and b with integer coefficients. Substituting backwards through the division steps expresses the gcd as a·x + b·y. This is Bézout's identity, and the integers x and y are the Bézout coefficients. They are not unique, but any valid pair will do.

Modular inverses

If gcd(a, m) = 1, Bézout gives a·x + m·y = 1. Reducing modulo m, a·x ≡ 1 (mod m), so x is the inverse of a. If the gcd is larger than 1, no inverse exists, since every multiple of a modulo m is divisible by that gcd. Inverses are what make division possible in modular arithmetic.

Speed and common mistakes

The number of division steps grows only with the number of digits: by Lamé's theorem it never exceeds about five times the digit count of the smaller number, and the slowest inputs are consecutive Fibonacci numbers. The most common hand-calculation errors are stopping one step early, dividing in the wrong order (always divide the larger number by the smaller) and losing a sign during back-substitution. Writing the quotients in a table, as the calculator does, makes each of these easy to spot.

Key formulas

• gcd(a, b) = gcd(b, a mod b), gcd(a, 0) = |a|
• a·x + b·y = gcd(a, b) (Bézout)
• a⁻¹ mod m = x mod m when a·x + m·y = 1

Solved example

Practice questions

Try each question first, then open the answer.