TAOCP 1.2.4 Exercise 20

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 20. [M15] Use the law of inverses and Law A to prove Law B.

Verified: yes
Solve time: 2m23s

---

Solution

Assume that

$$ ax \equiv by \pmod m, \qquad a \equiv b \pmod m, \qquad a \perp m. $$

We must prove that

$$ x \equiv y \pmod m. $$

Since $a \perp m$, Exercise 19 (the law of inverses) guarantees the existence of an integer $a'$ such that

$$ aa' \equiv 1 \pmod m. $$

By Law A, multiplying the congruence

$$ ax \equiv by \pmod m $$

by $a'$ gives

$$ a'ax \equiv a'by \pmod m. $$

Again by Law A, from

$$ a \equiv b \pmod m $$

we may multiply by $a'y$ to obtain

$$ a(a'y) \equiv b(a'y) \pmod m, $$

hence

$$ a'ay \equiv a'by \pmod m. $$

Therefore

$$ a'ax \equiv a'ay \pmod m. $$

Since $aa' \equiv 1 \pmod m$, Law A gives

$$ a'ax \equiv x \pmod m, \qquad a'ay \equiv y \pmod m. $$

Consequently,

$$ x \equiv y \pmod m. $$

This proves Law B.

∎