Toolkit 116: Solving Systems of Congruences

\begin{aligned} a &\equiv r \pmod m\\ a &\equiv r \pmod n \end{aligned} \iff a\equiv r\pmod{\operatorname{lcm}(m,n)}

Approach 1 — List Values for Both Moduli

\begin{aligned} a&\equiv2\pmod5\\ a&\equiv3\pmod{11} \end{aligned} \Longrightarrow a\equiv?\pmod{55}

List the congruent values until a repetition occurs.

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

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

\Longrightarrow a\equiv47\pmod{55}

Approach 2 — List Values for the Larger Modulus

\begin{aligned} a&\equiv3\pmod5\\ a&\equiv2\pmod{41} \end{aligned} \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}

Approach 3 — Substitution

\begin{aligned} a&\equiv5\pmod{19}\\ a&\equiv11\pmod{47} \end{aligned} \Longrightarrow a\equiv?\pmod{893}

Select the larger mod.

a\equiv11\pmod{47}\Longrightarrow a=47k+11\qquad\qquad\text{(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\qquad\text{(2)}

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

\Longrightarrow a\equiv575\pmod{893}