When does the multiplicative inverse $x^{-1} \mod N$ exist, and when does it not?

The multiplicative inverse $x^{-1} \mod N$ exists if and only if $\gcd(x, N) = 1$ — i.e., x and N are coprime (relatively prime).

Definition: $y \equiv x^{-1} \mod N$ means $y \cdot x \equiv 1 \mod N$

Example mod 9 ($\mathbb{Z}_9 = \{0, 1, 2, ..., 8\}$):

Elements 0, 3, 6 have no inverse because $\gcd(3, 9) = 3 \neq 1$ and $\gcd(6, 9) = 3 \neq 1$.

Key consequences:

• If $N = p$ is prime, then every element in $\{1, ..., p-1\}$ has an inverse (because $\gcd(a, p) = 1$ for all $a < p$)
• For $N = 26$ (affine cipher): $\gcd(14, 26) = 2 \neq 1$, so $14^{-1} \mod 26$ does NOT exist
• The number of elements with inverses mod N is exactly $\varphi(N)$ (Euler's phi function)

Tip: If $y \equiv x^{-1} \mod N$, then also $x \equiv y^{-1} \mod N$ — inverses are symmetric.

Go deeper:

• Modular multiplicative inverse (Wikipedia) — existence condition gcd(x,N)=1 and how to compute it.