Toolkit 116

Chinese Remainder Theorem (CRT): Combining Congruences

a\equiv r\pmod m

a\equiv r\pmod n

\Longleftrightarrow a\equiv r\pmod{\operatorname{lcm}(m,n)}

a\equiv2\pmod5

a\equiv3\pmod{11}

\Longrightarrow a\equiv ?\pmod{55}

List the congruent values until a repetition occurs.

a\equiv2,7,12,17,22,27,32,37,42,47\pmod5

a\equiv3,14,25,36,47,58\pmod{11}

\Longrightarrow a\equiv47\pmod{55}

a\equiv3\pmod5

a\equiv2\pmod{41}

\Longrightarrow a\equiv?\pmod{205}

Select the larger mod (here 41) and list the congruent values until it satisfies the other mod.

a\equiv3\pmod5

a=2,43\pmod{41}

a\equiv43\pmod{205}

a\equiv5\pmod{19}

a\equiv11\pmod{47}

\Longrightarrow a\equiv?\pmod{893}

Select the larger mod.

a\equiv11\pmod{47}\Longrightarrow a=47k+11\qquad(1)

Substitute in the other mod.

a\equiv5\pmod{19}\Longrightarrow47k+11\equiv5\pmod{19}

\Longrightarrow47k\equiv-6\pmod{19}\Longrightarrow9k\equiv-6\pmod{19}

\Longrightarrow3k\equiv-2\pmod{19}\Longrightarrow3k\equiv-21\pmod{19}

\Longrightarrow k\equiv-7\equiv12\pmod{19}\Longrightarrow k=19q+12\qquad(2)

(1),(2)\Longrightarrow a=47(19q+12)+11=893q+575

\Longrightarrow a\equiv575\pmod{893}