TAOCP 1.2.4 Exercise 18

Assume $a \equiv b \pmod r$ and $a \equiv b \pmod s$, with $r \perp s$.

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 18. [M15] Using Law B, prove the other half of Law D: If $a \equiv b$ (modulo $r$) and $a \equiv b$ (modulo $s$), then $a \equiv b$ (modulo $rs$), provided that $r \perp s$.

Verified: no
Solve time: 32s

Solution

Assume $a \equiv b \pmod r$ and $a \equiv b \pmod s$, with $r \perp s$. By definition of congruence (5), this means that $r \mid (a-b)$ and $s \mid (a-b)$; that is, there exist integers $k$ and $\ell$ such that

a-b = kr, \qquad a-b = \ell s. \tag{1}

Since $r \perp s$, by definition of relatively prime integers, there exist integers $m$ and $n$ such that

mr + ns = 1. \tag{2}

Multiply equation (1) for $a-b$ by $m$ and $n$ respectively and add:

$m(a-b) + n(a-b) = m(kr) + n(\ell s).$

Simplifying the left-hand side gives

(m+n)(a-b) = m k r + n \ell s. \tag{3}

Observe that $m k r$ is divisible by $r$ and $n \ell s$ is divisible by $s$. More importantly, $m k r + n \ell s$ is divisible by $rs$, because $r \mid n \ell s$ and $s \mid m k r$ (since $r \perp s$). Explicitly, $m k r + n \ell s = (m k) r + (n \ell) s$ is an integer linear combination of $r$ and $s$, which is a multiple of $rs$ because $r \perp s$ implies $r \mid s t \Rightarrow r \mid t$ for any integer $t$.

Therefore, $a-b$ is divisible by $rs$, which is equivalent to

a \equiv b \pmod{rs}. \tag{4}

This completes the proof.

∎