TAOCP 1.2.4 Exercise 14

Let $x \equiv 2 \pmod 3,$ $x \equiv 3 \pmod 5.$ Since $3 \perp 5$, Law D implies that these two congruences determine a unique congruence class modulo $15$.

taocpmathematicsalgorithmsvolume-1simple

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 14. ▶ [12] If $x \bmod 3 = 2$ and $x \bmod 5 = 3$, what is $x \bmod 15$?

Verified: yes
Solve time: 34s

Solution

Let

$x \equiv 2 \pmod 3,$

$x \equiv 3 \pmod 5.$

Since $3 \perp 5$, Law D implies that these two congruences determine a unique congruence class modulo $15$.

Write

$x=3k+2.$

Substituting into the second congruence gives

$3k+2 \equiv 3 \pmod 5,$

hence

$3k \equiv 1 \pmod 5.$

Now

$3\cdot 2=6\equiv 1 \pmod 5,$

so multiplying both sides by $2$ and using Law A yields

$k \equiv 2 \pmod 5.$

Therefore

$k=5m+2$

for some integer $m$, and hence

$x=3(5m+2)+2=15m+8.$

Thus

$x \equiv 8 \pmod{15}.$

Therefore

$\boxed{x \bmod 15 = 8}.$