Extended Euclidean Algorithm
What you'll learn: How to express the greatest common divisor (GCD) of two integers as a linear combination of those integers.
The Core Idea
The Euclidean Algorithm gives you the GCD of two numbers, but the Extended Euclidean Algorithm goes further: it finds integers x and y such that:
gcd(a, b) = ax + by
This equation is called a linear combination or Bézout's identity. It's incredibly useful in number theory—showing that you can "build" the GCD using the original numbers themselves.
How It Works
The Extended Euclidean Algorithm works backward through the steps of the regular Euclidean Algorithm. Here's the intuition:
- Run the standard Euclidean Algorithm forward, keeping track of all remainders
- Starting from the last nonzero remainder (the GCD), express it in terms of the previous two remainders
- Work backward, substituting each remainder until you express the GCD purely in terms of the original a and b
Example
Find gcd(240, 46) and express it as a linear combination:
Forward (Euclidean Algorithm):
- 240 = 46 × 5 + 10
- 46 = 10 × 4 + 6
- 10 = 6 × 1 + 4
- 6 = 4 × 1 + 2
- 4 = 2 × 2 + 0
So gcd(240, 46) = 2.
Backward (Extended):
- 2 = 6 − 4 × 1
- 2 = 6 − (10 − 6 × 1) × 1 = 6 × 2 − 10
- 2 = (46 − 10 × 4) × 2 − 10 = 46 × 2 − 10 × 9
- 2 = 46 × 2 − (240 − 46 × 5) × 9 = 240 × (−9) + 46 × 47
Check: 240(−9) + 46(47) = −2160 + 2162 = 2 ✓
Key Takeaway: The Extended Euclidean Algorithm not only finds gcd(a, b) but also discovers coefficients x and y satisfying gcd(a, b) = ax + by, revealing the deep structure behind divisibility.