What division means modulo n
In ordinary arithmetic you divide by multiplying by a reciprocal. Under a modulus there are no fractions, so dividing by a value means multiplying by its modular inverse: the number that multiplied by the original gives one modulo n. Inverses power modular fractions, binomial coefficients under a prime, and many counting formulas.
When an inverse exists
A value has an inverse modulo n exactly when it shares no common factor with n other than one, meaning they are coprime. If the modulus is a prime, every nonzero value is coprime to it, so every nonzero value has an inverse.
Two ways to compute it
- The extended Euclidean algorithm finds coefficients expressing the greatest common divisor as a combination of the value and the modulus. The coefficient on the value, reduced modulo n, is the inverse. This works whenever an inverse exists.
- Fermat's little theorem applies when the modulus is prime: the inverse equals the value raised to the modulus minus two, computed by fast modular exponentiation.
Key idea
Dividing modulo n means multiplying by a modular inverse, which exists when the value is coprime to n and is found by extended Euclid in general or Fermat's theorem under a prime modulus.