The site's sixth Number Theory entry, and it closes a forward reference from
Modular Exponentiation's own Complexity section.
Extended Euclidean Algorithm already answers "what's
the modular inverse of a mod m?" for any modulus — run the reduction that finds gcd(a, m), and (when that gcd
is 1) the coefficient it produces along the way is the inverse. This page is a second, narrower route
to the same number: when the modulus happens to be prime, the inverse falls straight out of
modular exponentiation — no gcd reduction, no second
algorithm, just one more call to the same modPow routine this site already built.
Miller–Rabin's own Pitfalls section
already lays out Fermat's Little Theorem in full: if p is prime and a
is not a multiple of p, then ap−1 ≡ 1 (mod p). This page doesn't
re-derive that — it uses it. Split the exponent: ap−1 = ap−2 ·
a, so the theorem says ap−2 · a ≡ 1 (mod p). Read that equation for what
it actually claims: ap−2 mod p is, by definition, the number that multiplies
a to give 1 mod p — the modular inverse. No back-substitution, no coefficient
tracking; just one modular exponentiation with a specific exponent.
Enter a and a modulus p, then compute the inverse two independent ways: the
Fermat route (modPow(a, p−2, p)) and the Extended Euclidean route (the same algorithm as
that page, run fresh here). 3, 7 and 3, 11 are both prime moduli — watch the
two routes agree. 3, 8 is the pitfall preset: 8 isn't prime, and the two routes stop agreeing
(see Pitfalls for how often, checked).
function modPow(base, exp, mod) { // identical to Modular Exponentiation's own routine
base = ((base % mod) + mod) % mod;
let result = 1n % mod;
while (exp > 0n) {
if (exp & 1n) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1n;
}
return result;
}
function modInverseFermat(a, p) { // p MUST be prime; a must not be a multiple of p
return modPow(a, p - 2n, p);
}That's the entire algorithm — one line, reusing a routine this site already has. The cost is the
restriction spelled out in the comment: it's only correct when p is genuinely prime, and the
function has no way to check that for you (see Pitfalls).
A composite modulus doesn't make the formula fail loudly — it makes it return a plausible-looking
wrong number. Fermat's Little Theorem is a statement about prime moduli; nothing in
modPow(a, p−2, p) checks that p actually is one. Take a = 3, p =
8: the Fermat route returns 1, but 3 × 1 mod 8 = 3, not 1 — 1 is not
3's inverse mod 8. The real inverse, from the Extended Euclidean route, is 3 (3 × 3 =
9 = 1×8 + 1, checked). This isn't a rare edge case: sweeping every composite modulus m
from 4 to 200 and every a coprime to it (8,050 checked (a, m) pairs total, using the Extended
Euclidean route as ground truth), the Fermat-route formula disagreed with the true inverse in 7,515
of 8,050 pairs — 93.4%. None of the 55 composite moduli checked in that sweep had zero mismatches.
The Extended Euclidean route has no such restriction — it only needs gcd(a, m) = 1, prime or
not — which is exactly why it stays the general-purpose tool and this page's shortcut stays a
prime-only convenience.
Using exponent p−1 instead of p−2 doesn't produce a
slightly-wrong inverse — Fermat's theorem itself guarantees it always returns exactly 1, for every valid
input. ap−1 mod p = 1 is the theorem this whole page is built on, so
this off-by-one isn't a computation that sometimes goes wrong — it's a fixed, theorem-guaranteed constant,
checked directly on three different (a, p) pairs (3 mod 7, 5 mod 13, 2 mod 101: all three return exactly 1).
It happens to be silently correct in exactly one case, a = 1, since 1 is its own inverse modulo
anything — everywhere else (any a > 1) it's a wrong answer that looks exactly as clean and
plausible as a right one.
When a is a multiple of p, no inverse exists at all — and the formula
doesn't error, it quietly returns 0. Fermat's theorem explicitly requires a not be a
multiple of p; feed it one anyway and every factor in the squaring chain is congruent to 0 mod
p, so the whole product collapses to 0. Checked: a = 7, p = 7 gives
modPow(7, 5, 7) = 0, while the true answer is that no inverse exists (the
Extended Euclidean route correctly reports gcd(7, 7) = 7 ≠ 1 and refuses to name one). 0 is
never a valid modular inverse of anything — multiplying by 0 can't produce 1 mod any modulus greater
than 1 — so this failure mode is at least easy to catch if a caller checks the answer, unlike the composite-
modulus case above, which returns numbers that look just as legitimate as correct ones.
O(log p) modular multiplications — identical to
Modular Exponentiation's own bound, because this
is that algorithm, called with one specific exponent. That's about the same order as Extended
Euclidean's O(log(min(a, p))) division steps, so neither route wins on asymptotic grounds alone.
The real trade-off is scope, not speed: Extended Euclidean works for any modulus with gcd(a, m) = 1,
prime or composite, while this route only works when p is prime — its appeal is reuse, not
generality, for code that already has a hardened modPow lying around (finite-field and
elliptic-curve cryptography routinely do) and would rather call it a second time than implement and maintain
an entirely separate gcd-based routine.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other thirteen Number Theory entries side by side.