Modular inverse calculator

How it works

The inverse of $a$ modulo $n$ is the number $x$ with $a \cdot x \equiv 1 \pmod n$. It plays the role of division in modular arithmetic: dividing by $a$ means multiplying by $a^{-1}$.

It exists exactly when $\gcd(a, n) = 1$. The extended Euclidean algorithm finds it: besides the gcd it keeps track of numbers $s, t$ with $s \cdot n + t \cdot a = \gcd(a, n)$ (Bézout’s identity). When the gcd is 1, reducing this modulo $n$ leaves $t \cdot a \equiv 1$, so $t$ is the inverse.

In RSA, the private exponent $d$ is the inverse of the public exponent $e$ modulo $\varphi(N)$: the classic small example is $17^{-1} \equiv 2753 \pmod{3120}$.