Modular Inverses via Fermat's Little Theorem
What You'll Learn
You'll learn how to quickly find the multiplicative inverse of a number modulo a prime using Fermat's Little Theorem, without needing the Extended Euclidean Algorithm.
The Core Idea
Recall that Fermat's Little Theorem states: if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p).
Now, let's rewrite this slightly:
a^(p-1) ≡ 1 (mod p)
a · a^(p-2) ≡ 1 (mod p)
This tells us something powerful: a^(p-2) acts as the multiplicative inverse of a modulo p!
Why? Because the definition of a modular inverse says that a · a^(-1) ≡ 1 (mod p). Comparing with our rearranged equation, we see that a^(-1) ≡ a^(p-2) (mod p).
When to Use This Method
This technique only works when your modulus is prime. If the modulus isn't prime, you must use the Extended Euclidean Algorithm instead.
Example
Find the inverse of 3 modulo 11:
- Here
a = 3andp = 11(prime) - Compute
3^(11-2) = 3^9 (mod 11) - Using repeated squaring:
3^9 = 19683 ≡ 4 (mod 11) - Verify:
3 · 4 = 12 ≡ 1 (mod 11)✓
The inverse of 3 modulo 11 is 4.
Why This Matters
This formula is elegant and especially useful in cryptography and competitive programming where you frequently need modular inverses under prime moduli. Instead of running the Extended Euclidean Algorithm, you can compute a single power using fast exponentiation.
Key Takeaway: When working modulo a prime p, the modular inverse of a is simply a^(p-2) mod p, giving you a direct formula: a^(-1) ≡ a^(p-2) (mod p).