## 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}$.