1. Reduce base
Take the base modulo p up front to keep numbers small.
base = base % modTyporithm · medium
Modular Inverse
▷ Interactive algorithm labmodular-inversemathfermatmod-arithmeticinverse
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Modular Inverse
Math & Number Theory
For a prime modulus p, the inverse of a is a^(p-2) mod p by Fermat's little theorem, found with fast modular exponentiation.
A modular inverse of a is the value x with a*x ≡ 1 (mod p) — division in modular arithmetic.
Fermat's little theorem says a^(p-1) ≡ 1 (mod p) for prime p and a not divisible by p, so a^(p-2) ≡ a^(-1).
Computing a^(p-2) with square-and-multiply runs in O(log p); for a composite modulus use the extended Euclidean algorithm instead.
Preparing algorithm lab…
01
inverse = a^(p-2) mod p.
02
Needs a prime modulus p.
03
Use extended Euclid when p is not prime.
function modPow(base, exp, mod) {
let result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 === 1) {
result = (result * base) % mod;
}
exp = Math.floor(exp / 2);
base = (base * base) % mod;
}
return result;
}
function modInverse(a, p) {
return modPow(a, p - 2, p);
}Read the implementation
Connect each part of the code to the concept before you type.
2. Multiply mod
Fold the base into the result on a set bit, reducing modulo p.
result = (result * base) % mod3. Square base
Square the base each step so the exponent is consumed in binary.
base = (base * base) % mod4. Fermat's exponent
By Fermat's little theorem a^(p-1) ≡ 1, so a^(p-2) is the inverse of a mod p.
return modPow(a, p - 2, p)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.