TAOCP 1.2.4 Exercise 23
Consider integers $a=2$, $b=8$, $r=4$, and $s=6$.
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 23. [M10] Give an example to show that Law D is not always true if $r$ is not relatively prime to $s$.
Verified: no
Solve time: 33s
Consider integers $a=2$, $b=8$, $r=4$, and $s=6$. Here $r$ and $s$ are not relatively prime since $\gcd(4,6)=2>1$. We examine the congruences modulo $r$ and $s$:
Modulo $r=4$, we have $a \equiv b \pmod{4}$ because $8-2=6$ is divisible by $4$.
Modulo $s=6$, we also have $a \equiv b \pmod{6}$ since $8-2=6$ is divisible by $6$.
However, the product $rs=24$ does not satisfy $a \equiv b \pmod{24}$ because $8-2=6$ is not divisible by $24$.
This demonstrates that Law D, which asserts $a \equiv b \pmod{rs}$ if and only if $a \equiv b \pmod{r}$ and $a \equiv b \pmod{s}$, can fail when $r$ and $s$ are not relatively prime. ∎