TAOCP 1.2.4 Exercise 22

Exercise 22. ▶ [M10] Give an example to show that Law B is not always true if $a$ is not relatively prime to $m$.

Verified: yes
Solve time: 3m11s

Take $m=6$ and $a=2$. Since $2$ and $6$ are not relatively prime, Law B need not hold. Let $x=1$ and $y=4$. Then

$$ ax=2\cdot1=2,\qquad ay=2\cdot4=8\equiv2\pmod6, $$

$$ ax\equiv ay\pmod6. $$

Also $a\equiv a\pmod6$. But

$$ x=1\not\equiv4=y\pmod6, $$

since $4-1=3$ is not a multiple of $6$. Thus the conclusion of Law B fails when $a\not\perp m$.

$$ \boxed{2\cdot1\equiv2\cdot4\pmod6,\ \text{but }1\not\equiv4\pmod6} $$