= Modular multiplicative inverse
{title2=$a^{-1}\pmod n$}
{wiki}
= Modular inverse
{synonym}
For <integers> $a$ and $n>1$, a modular multiplicative inverse is a <congruence class> $b$ satisfying $ab\equiv1\pmod 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\cdot7-2\cdot17=1$, so $5^{-1}\equiv7\pmod{17}$. The <modular congruence> $5x\equiv3\pmod{17}$ therefore has the unique solution class $x\equiv21\equiv4\pmod{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 https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf[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\equiv3\pmod{15}$ has no solution, while $5x\equiv10\pmod{15}$ has five solution classes, $x\equiv2,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>.
\Image[/modular-inverse-permutations.png]
{title=Multiplication by five is reversible modulo seventeen but collapses classes modulo fifteen}
Back to article page
