Apr 27, 2017

Being a unit in ZZn

$$ \text{$\overline{a}$ is invertible in $\mathbb{Z}_n$ iff $a$ and $n$ are relatively prime.}$$ The following proof from Pinter (p.228) is nice. Use a notation: $\overline{x} = x \pmod n$. Then, \begin{align*} & \text{$a$ and $n$ are relatively prime} \\ \Leftrightarrow\quad& \text{gcd}(a,n) = 1 \\ \Leftrightarrow\quad& sa + tn = 1 \quad (\exists s,t \in \mathbb{Z})\\ \Leftrightarrow\quad& 1 - sa = tn \\ \Leftrightarrow\quad& \overline{sa} = \overline{1} \\ \Leftrightarrow\quad& \overline{s}\:\overline{a} = \overline{1} \\ \end{align*}