Multiplicative Inverse in Ring of Integers Modulo m

Theorem

Let $\left({\Z_m, +_m, \times_m}\right)$ be the Ring of Integers Modulo m.

Then $\left[\!\left[{k}\right]\!\right]_m \in \Z_m$ has an inverse in $\left({\Z_m, \times_m}\right)$ iff $k \perp m$.

Proof

• First, suppose $k \perp m$. That is, $\gcd \left\{{k, m}\right\} = 1$.

Then, by Bézout's Identity, $\exists u, v \in \Z: u k + v m = 1$.

Thus $\left[\!\left[{u k + v m}\right]\!\right]_m = \left[\!\left[{u k}\right]\!\right]_m = \left[\!\left[{u}\right]\!\right]_m \left[\!\left[{k}\right]\!\right]_m = \left[\!\left[{1}\right]\!\right]_m$.

Thus $\left[\!\left[{u}\right]\!\right]_m$ is an inverse of $\left[\!\left[{k}\right]\!\right]_m$.

• Suppose $\exists u \in \Z: \left[\!\left[{u}\right]\!\right]_m \left[\!\left[{k}\right]\!\right]_m = \left[\!\left[{u k}\right]\!\right]_m = 1$.

Then $u k \equiv 1 \left({\bmod\, m}\right)$ and $\exists v \in \Z: u k + v n = 1$.

Thus from Bézout's Identity, $k \perp m$.

$\blacksquare$

Sources

• Iain T. Adamson: Introduction to Field Theory (1964)... (previous)... (next): $\S 1.1$: Example $4$