Course contentsShow
← Mathematics
Lesson 2745 of 3,12154. Number TheoryFree lesson

Modular Inverses via Fermat's Little Theorem

Find the multiplicative inverse of a modulo prime p using a^(p-2) ≡ a^(-1) (mod p).

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 = 3 and p = 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).