TAOCP 1.2.4 Exercise 17

By definition of congruence, the statement u \equiv v \pmod m means that $u-v$ is an integral multiple of $m$.

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 17. [M15] Prove Law A directly from the definition of congruence, and also prove half of Law D: If $a \equiv b$ (modulo $rs$), then $a \equiv b$ (modulo $r$) and $a \equiv b$ (modulo $s$). (Here $r$ and $s$ are arbitrary integers.)

Verified: yes
Solve time: 30s

Solution

By definition of congruence, the statement

$$ u \equiv v \pmod m $$

means that $u-v$ is an integral multiple of $m$.

Assume first that

$$ a \equiv b \pmod m,\qquad x \equiv y \pmod m. $$

Then there exist integers $j$ and $k$ such that

$$ a-b=jm,\qquad x-y=km. $$

For addition,

$$ (a+x)-(b+y)=(a-b)+(x-y)=jm+km=(j+k)m. $$

Hence $(a+x)-(b+y)$ is an integral multiple of $m$, so

$$ a+x \equiv b+y \pmod m. $$

For subtraction,

$$ (a-x)-(b-y)=(a-b)-(x-y)=jm-km=(j-k)m. $$

Hence $(a-x)-(b-y)$ is an integral multiple of $m$, so

$$ a-x \equiv b-y \pmod m. $$

For multiplication,

$$ \begin{aligned} ax-by &=ax-bx+bx-by \ &=(a-b)x+b(x-y) \ &=(jm)x+b(km) \ &=(jx+bk)m. \end{aligned} $$

Hence $ax-by$ is an integral multiple of $m$, so

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

This proves Law A.

Now assume

$$ a \equiv b \pmod{rs}. $$

Then there exists an integer $t$ such that

$$ a-b=t(rs). $$

Since

$$ a-b=(ts)r, $$

the difference $a-b$ is an integral multiple of $r$. Therefore

$$ a \equiv b \pmod r. $$

Similarly,

$$ a-b=(tr)s, $$

so $a-b$ is an integral multiple of $s$. Therefore

$$ a \equiv b \pmod s. $$

This proves the stated half of Law D.

This completes the proof.

∎