Modular multiplicative inverse ($a^{-1}(\mathrm{mod}n)$)

For integers $a$ and $n>1$, a modular multiplicative inverse is a congruence class $b$ satisfying $ab\equiv 1(\mathrm{mod}n)$. It exists exactly when $\gcd (a,n)=1$. Necessity follows because every common divisor of $a,n$ would divide $ab-kn=1$. Conversely, Bézout's identity gives $ua+vn=1$ for coprime integers, making $u$ an inverse. This is the basic bridge from greatest common divisor calculations to reversible modular arithmetic.

For example, $5\cdot 7-2\cdot 17=1$, so $5^{-1}\equiv 7(\mathrm{mod}17)$. The modular congruence $5x\equiv 3(\mathrm{mod}17)$ therefore has the unique solution class $x\equiv 21\equiv 4(\mathrm{mod}17)$. Multiplication by $5$ sends all seventeen residue classes to different classes; multiplying by $7$ reverses it. The inverse criterion and its algorithmic construction are presented in Ankur Moitra, MIT 18.200, 2024, modular inverses and Euclid's algorithm.

By contrast, $5$ has no modular inverse modulo $15$. Its products have only residues $0,5,10$. Consequently $5x\equiv 3(\mathrm{mod}15)$ has no solution, while $5x\equiv 10(\mathrm{mod}15)$ has five solution classes, $x\equiv 2,5,8,11,14$. Dividing by a noninvertible residue would discard this distinction. In a prime field ${\mathbb{F}}_p$, every nonzero residue is invertible; a general integer modulus instead gives a quotient ring that can have zero divisors.