What inverse means
Under a modulus there is no direct division, so to divide by a number you multiply by its modular inverse: the value that multiplies with the original to give one under the modulus. Such an inverse exists exactly when the number and the modulus share no common factor other than one.
Two ways to find it
- Extended Euclid. The extended greatest common divisor algorithm finds two coefficients expressing one as a combination of the number and the modulus. The coefficient on the number, reduced, is the inverse.
- By Fermat. When the modulus is prime, the inverse equals the number raised to the modulus minus two, computed with fast modular exponentiation.
The Euclid route works for any coprime modulus, while the Fermat route is simplest when the modulus is a known prime.
Where it appears
Modular inverses let you evaluate fractions and binomial coefficients under a prime modulus, which is common in counting problems that report answers modulo a large prime.
Key idea
A modular inverse replaces division under a modulus and exists when the number is coprime to the modulus, found either by extended Euclid in general or by Fermat when the modulus is prime.