Math Fundamentals18 sections · 814 units
Open in Course

Modular Inverse

(Division in modular arithmetic)

Division does not work directly with mod. You cannot compute (a / b) mod m by dividing. Instead you use the modular inverse.

The modular inverse of b mod m is a number b_inv such that (b × b_inv) mod m = 1. Then (a / b) mod m = (a × b_inv) mod m.

If m is prime, you can compute b_inv = b^(m-2) mod m using fast exponentiation. This is called Fermat's Little Theorem.