Case Western Reserve University

Modular Multiplicative Inverse

Notes

The modular multiplicative inverse of an integer $a\mod n$ is an integer x such that $ax \equiv \mod n$ . The modular multiplicative inverse $x$ of an integer may be denoted as $a^{-1}$ , and x exists if and only if the integers a and n are coprime, that is $gcd(a,n) = 1$ .

If n is prime, then every nonzero integer a that is not a multiple of n has a modular inverse. By Euler's totient theorem, if a and n are coprime, then $a^{\phi(n)} = 1 \mod n$ , where $\phi(n)$ is the totient function. Thus, $a^{\phi(n)} = 1 \mod n$ , where $a^{-1} = a^{\phi(n)-1}$ .