If the standard Euclidean algorithm is the “granddaddy” of algorithms, the Extended Euclidean Algorithm is its smarter, more versatile sibling.
In our previous article, we learned how to find the Greatest Common Divisor (GCD) of two numbers. But in the world of cryptography and advanced computer science, knowing the GCD isn’t enough. We often need to “reverse” the multiplication process in modular arithmetic.
This article explains how the Extended Euclidean Algorithm works, why it is the key to “division” in modular arithmetic, and how to solve problems that look impossible at first glance.
1. What is “Extended” About It?
The standard algorithm tells us what the GCD is. The extended version tells us how to express that GCD as a combination of the original numbers.
This is based on Bézout’s Identity. It states that for any integers a and b, there exist integers x and y such that:
$$ ax + by = \gcd(a, b) $$
Here, x and y are called Bézout coefficients. Finding these coefficients is crucial for solving linear equations and, most importantly, for encryption.
2. The Killer App: Modular Multiplicative Inverse
Why do we care about x and y? Because they allow us to perform division in modular arithmetic.
In standard math, if you want to divide by 7, you multiply by 1/7 (the reciprocal). In modular arithmetic (clock math), fractions don’t exist. Instead, we look for a Modular Multiplicative Inverse.
We want to find an integer x such that:
$$ a \cdot x \equiv 1 \pmod m $$
This is equivalent to solving the equation:
$$ ax + my = 1 $$
The Extended Euclidean Algorithm finds this x.
Note: An inverse only exists if a and m are coprime (i.e., their GCD is 1).
3. How It Works (Step-by-Step)
Let’s find the modular inverse of 23 modulo 52.
Goal: Find x such that 23x ≡ 1 (mod 52).
Phase 1: Forward (Standard Euclidean)
We perform the standard division until we hit a remainder of 0, keeping track of the equations.
Step 1:
$$ 52 = 2(23) + 6 $$
(Rewrite for remainder: $$ 6 = 52 – 2(23) $$)
Step 2:
$$ 23 = 3(6) + 5 $$
(Rewrite for remainder: $$ 5 = 23 – 3(6) $$)
Step 3:
$$ 6 = 1(5) + 1 $$
(Rewrite for remainder: $$ 1 = 6 – 1(5) $$)
Step 4:
$$ 5 = 5(1) + 0 $$
(Stop here. GCD is 1)
Phase 2: Backward (Substitution)
Now, we start with the equation for the GCD (1) and substitute back up the chain.
Start with Eq 3:
$$ 1 = 6 – 1(5) $$
Substitute Eq 2 (replace 5):
$$ 1 = 6 – 1(23 – 3(6)) $$
$$ 1 = 1(6) – 1(23) + 3(6) $$
$$ 1 = 4(6) – 1(23) $$
Substitute Eq 1 (replace 6):
$$ 1 = 4(52 – 2(23)) – 1(23) $$
$$ 1 = 4(52) – 8(23) – 1(23) $$
$$ 1 = 4(52) – 9(23) $$
Result:
$$ -9(23) + 4(52) = 1 $$
This means our coefficient for 23 is -9.
In modular arithmetic, we prefer positive numbers.
$$ -9 \pmod{52} = 43 $$
Verification:
$$ 23 \times 43 = 989 $$
$$ 989 \div 52 = 19 \text{ with a remainder of } 1. $$
It works!
4. Python Implementation
Doing this by hand is tedious. Here is the recursive Python implementation used by cryptographers.
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
else:
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
def mod_inverse(a, m):
gcd, x, y = extended_gcd(a, m)
if gcd != 1:
raise Exception('Modular inverse does not exist')
else:
return x % m
# Example
print(f"Inverse of 23 mod 52 is: {mod_inverse(23, 52)}")5. Practice Problems
To truly understand the Extended Euclidean Algorithm, try solving these problems.
Problem Set A: Bézout’s Identity
Objective: Express the GCD as a linear combination.
Problem: Find integers x and y such that 240x + 46y = gcd(240, 46).
Click to reveal answer
GCD is 2. The equation is:
$$ 240(-9) + 46(47) = 2 $$
So, x = -9, y = 47.
Problem Set B: Cryptography Basic
Objective: Find the modular inverse.
Problem: You are encrypting a message. You need to find the inverse of 7 modulo 26.
Click to reveal answer
Answer is 15. Because:
$$ 7 \times 15 = 105 $$
$$ 105 \pmod{26} = 1 $$
Problem Set C: The Impossible Case
Objective: Identify when no solution exists.
Problem: Find the inverse of 6 modulo 9.
Click to reveal answer
Impossible.
$$ \gcd(6, 9) = 3 $$
Since the GCD is not 1, an inverse does not exist (numbers must be coprime).
Conclusion
The Extended Euclidean Algorithm is the bridge between simple arithmetic and the complex algebra that secures the internet. By allowing us to find inverses, it makes algorithms like RSA possible.
If you enjoyed this technical deep dive, you might want to revisit our article on The Euclidean Algorithm to see where it all began.
