## If two integers are relatively prime, then they are invertible mod each other

Let $n \in \mathbb{Z}$, $n > 1$, and let $a \in \mathbb{Z}$ with $1 \leq a \leq n$. Prove that if $a$ and $n$ are relatively prime then there is an integer $c$ with $ac = 1 \mod n$.

Suppose $a$ and $n$ satisfy the hypotheses, with $\mathsf{gcd}(a,n) = 1$. Then there exist integers $c$ and $b$ such that $ac + nb = 1$. Reducing mod n gives $ac = 1 \mod n$.