True or false: "$3^{-1} \mod N$ can always be computed."

False — $3^{-1} \mod N$ exists only when $\gcd(3, N) = 1$. If $N$ is a multiple of 3 (like $N = 9, 15, 21, ...$), the inverse does not exist.

When it works: $3^{-1} \mod 7 = 5$ (since $5 \cdot 3 = 15 \equiv 1 \mod 7$) ✓ When it fails: $3^{-1} \mod 9$ → no solution exists (since $\gcd(3, 9) = 3 \neq 1$)

The general rule: $x^{-1} \mod N$ exists ⟺ $\gcd(x, N) = 1$

Why this matters:

• In RSA, we compute $e^{-1} \mod \varphi(N)$ — this only works because we specifically choose $e$ such that $\gcd(e, \varphi(N)) = 1$
• In the affine cipher, the parameter $a$ must satisfy $\gcd(a, 26) = 1$, otherwise decryption is impossible

Tip: Most calculators and tools (TI-89, Excel) cannot reliably compute modular inverses — use Wolfram Alpha, Maple, or Python's pow(3, -1, N) instead.

Go deeper:

• Modular multiplicative inverse (Wikipedia) — the coprimality condition for an inverse to exist.