Difficulty: Intermediate | Prerequisites: Euclidean algorithm study notes, basic proof by induction, modular arithmetic.
This topic extends the Euclidean algorithm so it returns not just the GCD but also integer coefficients a and b satisfying ax + by = gcd(x, y). Those coefficients unlock modular inverses, which are central to RSA encryption and many other number-theoretic algorithms covered later in EECS 376. You need to be comfortable with the basic Euclidean algorithm and with proof by induction before tackling this.
The Extended Euclidean algorithm computes gcd(x, y) and simultaneously finds integers a, b such that ax + by = gcd(x, y). This result (Bezout's identity) lets you compute modular inverses: if gcd(x, m) = 1, then a from ax + bm = 1 gives x^{-1} mod m = a mod m.
Bezout's identity
For any positive integers x and y, there exist integers a and b such that ax + by = gcd(x, y). In simple terms, you can always "build" the GCD from x and y using integer multiples (which may be negative).
Bezout coefficients
The pair (a, b) in ax + by = gcd(x, y). These are not unique, but the Extended Euclidean algorithm produces one specific pair.
Extended Euclidean algorithm
A modification of the standard Euclidean algorithm that tracks the coefficients a and b through each recursive call and returns the triple (g, a, b).
Modular inverse
The inverse of x modulo m, written x^{-1} (mod m), is the integer a such that x · a is congruent to 1 (mod m). It exists if and only if gcd(x, m) = 1. Think of it as "division" in modular arithmetic.
The Extended Euclidean algorithm is given in the homework with three lines marked "???". The completed lines are:
Line 7: g = g' (the GCD passes through unchanged from the recursive call)
Line 8: a = b'
Line 9: b = a' - q · b'
Here, q = floor(x / y) is the quotient from line 5, and (g', a', b') is the result of the recursive call ExtendedEuclid(y, r).
By induction, the recursive call returns (g', a', b') such that a'y + b'r = g' and g' = gcd(y, r) = gcd(x, y).
Since r = x - qy, substitute:
a'y + b'(x - qy) = g' b'x + (a' - qb')y = g'
So setting a = b' and b = a' - qb' gives ax + by = g = gcd(x, y).
Trace the algorithm:
ExtendedEuclid(293, 62): q = 4, r = 45
ExtendedEuclid(62, 45): q = 1, r = 17
ExtendedEuclid(45, 17): q = 2, r = 11
ExtendedEuclid(17, 11): q = 1, r = 6
ExtendedEuclid(11, 6): q = 1, r = 5
ExtendedEuclid(6, 5): q = 1, r = 1
ExtendedEuclid(5, 1): q = 5, r = 0
ExtendedEuclid(1, 0): returns (1, 1, 0)
Unwinding:
(5, 1): g = 1, a = 0, b = 1 - 5·0 = 1. Check: 0·5 + 1·1 = 1.
(6, 5): g = 1, a = 1, b = 0 - 1·1 = -1. Check: 1·6 + (-1)·5 = 1.
(11, 6): g = 1, a = -1, b = 1 - 1·(-1) = 2. Check: (-1)·11 + 2·6 = 1.
(17, 11): g = 1, a = 2, b = -1 - 1·2 = -3. Check: 2·17 + (-3)·11 = 1.
(45, 17): g = 1, a = -3, b = 2 - 2·(-3) = 8. Check: (-3)·45 + 8·17 = 1.
(62, 45): g = 1, a = 8, b = -3 - 1·8 = -11. Check: 8·62 + (-11)·45 = 1.
(293, 62): g = 1, a = -11, b = 8 - 4·(-11) = 52. Check: (-11)·293 + 52·62 = -3223 + 3224 = 1.
So the Bezout coefficients are a = -11, b = 52.
From the example above, (-11)·293 + 52·62 = 1. Reading this modulo 293:
52·62 = 1 (mod 293)
So 62^{-1} mod 293 = 52.
The general procedure: run ExtendedEuclid(m, x). If the GCD is 1, the coefficient of x, taken mod m, is the modular inverse.
Bezout's identity:
ax + by = gcd(x, y) for some integers a, b
Coefficient back-substitution (the recursive step):
g = g', a = b', b = a' - floor(x/y) · b'
Modular inverse from Bezout coefficients:
If ax + bm = 1, then x^{-1} mod m = a mod m
Modular inverses are the backbone of RSA encryption. The private key is computed as the modular inverse of the public exponent modulo a value derived from the prime factors. Without the Extended Euclidean algorithm (or an equivalent), RSA key generation would not work. Modular inverses also appear in Chinese Remainder Theorem applications, error-correcting codes, and secret-sharing schemes.
Students often mix up the roles of a' and b' when back-substituting. The coefficient of x in the current call comes from b' (the coefficient of the remainder in the recursive call), not a'.
A common error is forgetting that the modular inverse of x mod m is the coefficient of x, not the coefficient of m, in Bezout's identity.
Students sometimes assume modular inverses always exist. They exist only when gcd(x, m) = 1. If the GCD is greater than 1, there is no inverse.
When computing the inverse, students forget to reduce modulo m. The Bezout coefficient a can be negative, so you need to take a mod m (adding m if a is negative) to get the inverse in the range [0, m-1].
⚠️ Completing lines 7-9 of the Extended Euclidean algorithm is a classic exam question. Memorise the back-substitution: g = g', a = b', b = a' - q·b'.
⚠️ Be able to trace the algorithm by hand and verify each step. The examiner may give you a pair of numbers and ask for the Bezout coefficients.
⚠️ Know how to go from Bezout coefficients to a modular inverse in one step. This is tested frequently in the cryptography portions of the course.
Fill in the blank: In the Extended Euclidean algorithm, the coefficient a in the current call equals ___ from the recursive call. (b')
True or false: The modular inverse of 7 mod 10 exists. (True: gcd(7, 10) = 1.)
True or false: The modular inverse of 6 mod 9 exists. (False: gcd(6, 9) = 3, not 1.)
Fill in the blank: If 3·293 + (-14)·62 = 11, can you read off 62^{-1} mod 293 from this? ___ (No: the right-hand side must be 1, not 11. Bezout's identity gives the inverse only when the GCD is 1 and the equation equals 1.)
Q: Run ExtendedEuclid(35, 15). What are the Bezout coefficients?
A: gcd(35, 15): 35 = 2·15 + 5. gcd(15, 5): 15 = 3·5 + 0. gcd(5, 0) returns (5, 1, 0). Back-substitute for (15, 5): g = 5, a = 0, b = 1 - 3·0 = 1. Check: 0·15 + 1·5 = 5. Back-substitute for (35, 15): g = 5, a = 1, b = 0 - 2·1 = -2. Check: 1·35 + (-2)·15 = 35 - 30 = 5. Bezout coefficients: a = 1, b = -2.
Q: Find the inverse of 17 modulo 43.
A: Run ExtendedEuclid(43, 17). 43 = 2·17 + 9. 17 = 1·9 + 8. 9 = 1·8 + 1. 8 = 8·1 + 0. Unwinding: (9, 8) gives a = 1, b = -1. (17, 9) gives a = -1, b = 1 - 1·(-1) = 2. (43, 17) gives a = 2, b = -1 - 2·2 = -5. Check: 2·43 + (-5)·17 = 86 - 85 = 1. So 17^{-1} mod 43 = -5 mod 43 = 38.
Q: Explain in one sentence why the GCD does not change through the recursive calls of the Extended Euclidean algorithm.
A: Because gcd(x, y) = gcd(y, x mod y) for all x, y with y > 0, so each recursive call computes the GCD of a pair with the same GCD as the original.
This extends the Euclidean algorithm from the previous study notes. The modular inverse concept is essential for RSA and other public-key cryptosystems studied later in EECS 376. Bezout's identity also underpins the proof that if p is prime and p divides ab, then p divides a or p divides b, a fact used throughout number theory and algebra.
Extended Euclidean algorithm, Bezout's identity, Bezout coefficients, modular inverse, multiplicative inverse mod m, back-substitution, RSA key generation, coprime, relatively prime, EECS 376, number theory, gcd coefficients