Law of Inverses (Modulo Arithmetic)

Theorem

Let $m, n \in \Z$.

Then:

$\exists n' \in \Z: n n' \equiv d \left({\bmod\, m}\right)$

where $d = \gcd \left\{{m, n}\right\}$.

Corollary

Let $m, n \in \Z$ such that $m \perp n$, i.e. such that $m$ and $n$ are coprime.

Then:

$\exists n' \in \Z: n n' \equiv 1 \left({\bmod\, m}\right)$

Proof

We have that $d = \gcd \left\{{m, n}\right\}$.

So:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \exists a, b \in \Z: am + bn = d\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Bézout's Identity
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle am = d - bn\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle d - bn \equiv 0 \left({\bmod\,m}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of congruence
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle bn \equiv d \left({\bmod\,m}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Modulo Addition: add $bn$ to both sides of congruence

So $b$ (in the above) fits the requirement for $n'$ in the assertion to be proved.

$\blacksquare$

Proof of Corollary

We have that $m \perp n$.

That is, $\gcd \left\{{m, n}\right\} = 1$.

The result follows directly.

$\blacksquare$

Note

In the equivalence $n n' \equiv 1 \left({\bmod\, m}\right)$ note that from Euler's Theorem:

$n' \equiv n^{\phi \left({n}\right) - 1} \left({\bmod\, m}\right)$

where $\phi \left({n}\right)$ is the Euler $\phi$ function.

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.4$: Exercises $19, \, 28$