modular-inverse-coprime-property

Wed Apr 01 2026

There are two ways to compute modular inverses: Fermat's little theorem and the extended Euclidean algorithm. Fermat gives you $a^{-1} \equiv a^{p-1-1} \pmod{p}$ directly, which works but requires exponentiation. The extended Euclidean algorithm doesn't use this trick at all. It just adds additional bookkeeping to the standard GCD computation to find the inverse, and it's more efficient.

But why does the extended Euclidean algorithm actually work? And why does the inverse only exist when $\gcd(a, n) = 1$?

The Diophantine equation connection

The extended Euclidean algorithm works because there will always exist a solution for the Diophantine equation $a \cdot x + n \cdot y = \gcd(a, n)$. If we take $\bmod\;n$ on both sides, the $n \cdot y$ term vanishes and we get:

$a \cdot x \equiv \gcd(a, n) \pmod{n}$

When $\gcd(a, n) = 1$, this becomes $a \cdot x \equiv 1 \pmod{n}$, which means $x$ is the inverse of $a$ in $\mathbb{Z}_n$. So the inverse exists if and only if $a$ and $n$ are coprime.

The time complexity is $O(\log(\min(a, n)))$. Why not $\max$?

$\mathbb{Z}_n^*$ as a group

$\mathbb{Z}_n^* = \{a \in \mathbb{Z}_n \mid \gcd(a, n) = 1\}$ is the set of elements in $\mathbb{Z}_n$ that are coprime to $n$. It doesn't include 0. The size of this group is $\varphi(n)$, Euler's totient function.

To verify it's actually a group, check the four axioms:

1. Closure under multiplication. Let $x, y \in \mathbb{Z}_n^*$. Since both $x$ and $y$ are coprime with $n$, their product is also coprime with $n$ (i.e., $\gcd(x \cdot y, n) = 1$). Now $x \cdot y \bmod n \equiv x \cdot y - k \cdot n$ for some integer $k$. We need $\gcd(x \cdot y - k \cdot n,\; n) = 1$.
2. Associativity. Trivial.
3. Identity. The element 1.
4. Inverses. Every element has an inverse because they are coprime with $n$, so a solution to the Diophantine equation exists since their $\gcd$ with $n$ is 1.

Double-and-add is fast exponentiation in different notation

"Double and add" and fast exponentiation are basically the same algorithm. They just differ in notation.

Double-and-add computes $n \cdot P$: scalar multiplication is just repeated point addition. Compute $P, 2P, 4P, \ldots, 2^i P$ by doubling, until $2^i \leq n$. Add $2^i P$ to the result whenever the $i$-th bit is set in $n$. This runs in $O(\log n)$.

Fast exponentiation computes $X^y$: scalar exponentiation is just repeated multiplication. Compute $X, X^2, X^4, \ldots, X^{2^i}$ by squaring, until $2^i \leq y$. Multiply $X^{2^i}$ into the result whenever the $i$-th bit is set in $y$. This runs in $O(\log y)$.