Exercise 850Number theory › CongruencesL1Added 3 Nov 2026

Inverse via Fermat

#Fermat#inverse#modular arithmetic

Statement

Let $p$ be prime and $a\not\equiv0\pmod p$ . Show that $a^{-1}\equiv a^{p-2}\pmod p$ .

Hint

Multiply $a^{p-1}\equiv1$ by $a^{-1}$ .

Show solutionHide solution

Fermat. $a^{p-1}\equiv1\pmod p$ , so $a\cdot a^{p-2}\equiv1\pmod p$ .

Inverse. By uniqueness of the inverse mod $p$ , $a^{-1}\equiv a^{p-2}\pmod p$ .

Conclusion. Inverses mod prime $p$ can be computed via fast exponentiation.

Example. In $\mathbb{F}_{11}$ : $5^{-1}\equiv5^9\equiv9\pmod{11}$ (since $5\cdot9=45\equiv1$ ).