TAOCP 1.2.4 Exercise 19

Since $n \perp m$, the extended Euclidean algorithm (Algorithm 1.

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 19. ▶ [M10] (Law of inverses.) If $n \perp m$, there is an integer $n'$ such that $nn' \equiv 1$ (modulo $m$). Prove this, using the extension of Euclid’s algorithm (Algorithm 1.2.1E).

Verified: yes
Solve time: 30s

Since $n \perp m$, the extended Euclidean algorithm (Algorithm 1.2.1E) produces integers $u$ and $v$ such that

$un + vm = 1.$

Reducing both sides modulo $m$ gives

$un + vm \equiv 1 \pmod m \implies un \equiv 1 \pmod m,$

because $vm \equiv 0 \pmod m$. Therefore, setting $n' = u$ yields an integer satisfying

$nn' \equiv 1 \pmod m.$

This completes the proof. ∎