> [!NOTE] **Theorem** ($[a]_{n}$ is unit iff $a$ and $n$ are coprime) > Let $[a]_{m} \in \mathbb{Z} \text{/} m\mathbb{Z}.$ Then $[a]_{m}$ is a [[Unit in Integers Modulo n|unit]] iff $a$ and $m$ are [[Coprime Integers|coprime]]. *Proof*. ($\implies$) Suppose $[a]_{m}$ is a unit in $\mathbb{Z} \text{/}m\mathbb{Z}$. Then there is some $[b]_{m} \in \mathbb{Z} \text{/}m\mathbb{Z}$ such that $ab \equiv 1 \pmod{m}.$ Thus there is some $k \in \mathbb{Z}$ such that $ab-1 = km$. Write $g= \gcd(a,m)$. Then $g\mid a$ and $g\mid m$. So $g\mid(ab-km) = 1$. Hence $g=1$. ($\impliedby$) Conversely, suppose $\gcd(a,m) =1.$ Using [[Extended Euclidean Algorithm|extended Euclidean algorithm]], we can write $1=ba+cm$ for Bézout coefficients $b,c \in \mathbb{Z}.$ Thus $ab \equiv 1 \pmod{m}$. Hence $[a]_{m}$ is a unit, with multiplicative inverse $[b]_{m}.$