Euler’s theorem

Euler’s theorem may be used to compute modular inverses. According to the theorem, if $a$ is coprime to $m$, that is, $\gcd(a, m) = 1$, then

$$a^{\varphi(m)} \equiv 1 \pmod{m}$$

where $\varphi$ is Euler’s totient function. A modular multiplicative inverse can be found directly with:

$$a^{\varphi(m) - 1} \equiv a^{-1} \pmod{m}$$

Computing $a^{\varphi(m) - 1}$ can be done using modular exponentiation.