Difficulty: Intermediate | Prerequisites: Euclidean algorithm, basic modular arithmetic, mathematical induction.
The standard Euclidean algorithm gives you the GCD of two numbers, but for many applications in cryptography and number theory you need more: you need integers a and b such that ax + by = gcd(x, y). The Extended Euclidean Algorithm does exactly this, and it leads directly to computing modular inverses, which are essential for RSA encryption and modular arithmetic in general. This material builds on the Euclidean algorithm from Problems 1 and 2, so make sure you are comfortable with how GCD computation works before diving in.
The Extended Euclidean Algorithm augments the standard GCD computation to also find integers a, b such that ax + by = gcd(x, y). This result, called Bezout's identity, lets you compute modular inverses: if gcd(x, y) = 1, the coefficient b gives you the inverse of y modulo x. The whole thing runs in O(log(x + y)) time, same as the standard version.
Bezout's identity
For any integers x, y, the smallest positive integer expressible as ax + by (for integer a, b) is gcd(x, y). In simple terms, you can always "combine" x and y with integer multipliers to produce their GCD.
Bezout coefficients
The integers a and b in the equation ax + by = gcd(x, y). Think of them as the specific multipliers that combine x and y to yield the GCD.
Extended Euclidean Algorithm
A modification of the standard Euclidean algorithm that computes not only gcd(x, y) but also the Bezout coefficients a and b. In simple terms, it tracks extra bookkeeping during the GCD computation to recover the linear combination.
Modular inverse
The inverse of y modulo x is an integer a such that y * a ≡ 1 (mod x). It exists if and only if gcd(x, y) = 1. Think of it as "division" in modular arithmetic: multiplying by a undoes multiplication by y.
Coprime (relatively prime)
Two integers x and y are coprime if gcd(x, y) = 1. In simple terms, they share no common factor other than 1. This is the condition required for a modular inverse to exist.
Input: integers x > y >= 0. Output: a triple (g, a, b) where g = gcd(x, y) and ax + by = g.
If y = 0, return (x, 1, 0). Base case: 1x + 0y = x = gcd(x, 0).
Otherwise, write x = qy + r where 0 <= r < y.
Recursively compute (g', a', b') = ExtendedEuclid(y, r).
Set g = g', a = b', b = a' - b'*q.
Return (g, a, b).
The key step is line 4. The recursive call gives us a'*y + b'*r = g'. We need to convert this into coefficients for x and y.
By induction, the recursive call returns g' = gcd(y, r) with a'*y + b'*r = g'.
Since gcd(x, y) = gcd(y, r), we have g = g'.
Substitute r = x - qy into the Bezout equation:
a'y + b'r = a'y + b'(x - qy) = b'x + (a' - b'q)y = gSo setting a = b' and b = a' - b'*q gives ax + by = g, as required.
Trace the recursion:
ExtendedEuclid(293, 62): 293 = 4*62 + 45, recurse on (62, 45)
ExtendedEuclid(62, 45): 62 = 1*45 + 17, recurse on (45, 17)
ExtendedEuclid(45, 17): 45 = 2*17 + 11, recurse on (17, 11)
ExtendedEuclid(17, 11): 17 = 1*11 + 6, recurse on (11, 6)
ExtendedEuclid(11, 6): 11 = 1*6 + 5, recurse on (6, 5)
ExtendedEuclid(6, 5): 6 = 1*5 + 1, recurse on (5, 1)
ExtendedEuclid(5, 1): 5 = 5*1 + 0, recurse on (1, 0)
ExtendedEuclid(1, 0): base case, return (1, 1, 0)
Unwinding gives (g, a, b) = (1, -11, 52). Verify: 293 * (-11) + 62 * 52 = -3223 + 3224 = 1.
If gcd(x, y) = 1, then Bezout's identity gives us ax + by = 1 for some integers a, b.
Taking both sides modulo x:
ax + by \equiv 1 \pmod{x}Since ax ≡ 0 (mod x), this simplifies to by ≡ 1 (mod x). So b is the modular inverse of y modulo x.
From ExtendedEuclid(293, 62), we got a = -11, b = 52, so:
1 = (-11) * 293 + 52 * 62
Reduce modulo 293:
(-11) * 293 ≡ 0 (mod 293)
So 1 ≡ 52 * 62 (mod 293)
Therefore 62^{-1} ≡ 52 (mod 293).
Note: the homework solution has a typo, writing "52 * 63" in one line, but the correct value is 52 * 62 = 3224, and 3224 mod 293 = 3224 - 11*293 = 3224 - 3223 = 1. The answer 52 is correct.
The inverse of y modulo x exists if and only if gcd(x, y) = 1. If gcd(x, y) = d > 1, then every linear combination ax + by is a multiple of d, so you can never get ax + by = 1.
Extended Euclidean recurrence (the core step):
g \leftarrow g', \quad a \leftarrow b', \quad b \leftarrow a' - b'qBezout's identity:
\gcd(x, y) = ax + by \quad \text{for some integers } a, bModular inverse from Bezout coefficients:
If ax + by = 1, then y^{-1} ≡ b (mod x).
Base case:
\gcd(x, 0) = x = 1 \cdot x + 0 \cdot 0Modular inverses are central to RSA encryption. In RSA, the public and private keys are computed using the Extended Euclidean Algorithm to find the modular inverse of the public exponent modulo Euler's totient. Without this algorithm, key generation in RSA would not be practical. Modular arithmetic and Bezout's identity also appear in error-correcting codes, Chinese Remainder Theorem applications, and cryptographic hash functions.
Students often forget to handle the sign of the Bezout coefficients. The coefficient b from Extended Euclid can be negative. To get a positive modular inverse, add the modulus: if b < 0, then b + x is the positive representative.
A common mistake is trying to compute a modular inverse when gcd(x, y) > 1. The inverse does not exist in that case. Always check that the two numbers are coprime first.
Students sometimes confuse the roles of a and b. In the equation ax + by = g, the coefficient a goes with x and b goes with y. When computing y^{-1} mod x, the relevant coefficient is b (the one attached to y), not a.
Some students try to compute modular inverses by trial multiplication rather than using the Extended Euclidean Algorithm. This works for small numbers but is far too slow for cryptographic-size integers.
⚠️ Know the Extended Euclidean Algorithm's recurrence: g = g', a = b', b = a' - b'q. This is a standard exam question.
⚠️ Be able to prove correctness by substitution: show that ax + by = g using a'y + b'r = g' and r = x - qy.
⚠️ Know how to extract a modular inverse from Bezout coefficients. The step from ax + by = 1 to y^{-1} ≡ b (mod x) is commonly tested.
⚠️ Remember the existence condition: y^{-1} mod x exists if and only if gcd(x, y) = 1.
True or false: The Extended Euclidean Algorithm has a worse time complexity than the standard Euclidean Algorithm. False (same O(log(x+y)) complexity).
Fill in the blank: In ExtendedEuclid, the base case returns (x, ___, ___). (x, 1, 0).
True or false: 62 has a modular inverse modulo 293 because gcd(62, 293) = 1. True.
Fill in the blank: If ExtendedEuclid(x, y) returns (g, a, b), then ax + by = ___. g = gcd(x, y).
True or false: Every integer has a modular inverse modulo every other integer. False (only when they are coprime).
Q: State the recurrence for the Extended Euclidean Algorithm. Given that ExtendedEuclid(y, r) returns (g', a', b'), what are g, a, and b?
A: g = g', a = b', b = a' - b'*q, where q = floor(x/y).
Q: Prove that setting a = b' and b = a' - b'q gives ax + by = g.
A: By induction, a'y + b'r = g'. Substitute r = x - qy: b'x + (a' - b'q)y = b'x + a'y - b'qy = a'y + b'(x - qy) = a'y + b'r = g'. So ax + by = g with a = b', b = a' - b'q.
Q: Find 62^{-1} (mod 293) using the Extended Euclidean Algorithm.
A: ExtendedEuclid(293, 62) gives (1, -11, 52). Since (-11)293 + 5262 = 1, reducing modulo 293 gives 52*62 ≡ 1 (mod 293). So 62^{-1} ≡ 52 (mod 293).
Q: Does 6^{-1} (mod 9) exist? Why or why not?
A: No. gcd(6, 9) = 3 ≠ 1, so 6 and 9 are not coprime, and no integer a satisfies 6a ≡ 1 (mod 9).
Q: If ExtendedEuclid(x, y) returns a negative coefficient b, how do you find the positive representative of y^{-1} mod x?
A: Add x to b. Since b ≡ b + x (mod x), the positive representative is b + x.
The Extended Euclidean Algorithm is the computational backbone of RSA key generation (covered in later EECS 376 material and in EECS 388). Bezout's identity also underlies the Chinese Remainder Theorem, which lets you solve systems of modular equations. The proof technique here (induction on the recursive structure) is the same pattern used throughout EECS 376 for proving correctness of recursive algorithms.
Extended Euclidean Algorithm, Bezout's identity, Bezout coefficients, modular inverse, modular multiplicative inverse, coprime, relatively prime, RSA, key generation, gcd, greatest common divisor, linear combination, EECS 376 Homework 1, University of Michigan, Foundations of Computer Science, number theory, modular arithmetic, Chinese Remainder Theorem