Existence of inverses modulo n

Remarks

If $\gcd(a, n) = 1$, Bézout's identity gives integers $x$ and $y$ with $a x + n y = 1$. Then $a x \equiv 1 \pmod n$. Conversely, if $a x \equiv 1 \pmod n$, then $a x + n y = 1$ for some integer $y$, so each common divisor of $a$ and $n$ divides $1$. The extended Euclidean algorithm computes the inverse. For example, $4$ has no inverse modulo $6$, because $\gcd(4, 6) = 2$.