# Solving Chinese Remainder Theorem Algebraically

I am doing a practice problem for my final which asks:

Solve the following Chinese Remainder Theorem: $$x \equiv 2 \pmod{3}, \\ x \equiv 3 \pmod{5}, \\ x \equiv 5 \pmod{7}, \\ x \equiv 7 \pmod{11} \\ x \equiv 11 \pmod{13}$$

From the first I can conclude that $x = 3k + 2$ for some $k \in \mathbb{Z}$.

Now I can apply that to the second equation which gives $3k+2 \equiv 3 \pmod{5}.$

Then I get lost here. Do I subtract $2$ and solve $3k \equiv 1 \pmod{5}$?

I don't have a solid understanding of solving the Chinese Remainder Theorem algebraically in general.

\begin{align} x &\equiv 2 \pmod 3 \\ x &= 2 + 3a \\ \hline x &\equiv 3 \pmod 5 \\ 2+3a &\equiv 3 \pmod 5 \\ 3a &\equiv 1 \pmod 5 \\ a &\equiv 2 \pmod 5 \\ a &= 2 + 5b \\ x &= 2 + 3(2 + 5b)\\ x &= 8 + 15b \\ \hline x &\equiv 5 \pmod 7 \\ 8 + 15b &\equiv 5 \pmod 7 \\ 1 + b &\equiv 5 \pmod 7 \\ b &\equiv 4 \pmod 7 \\ b &= 4 + 7c \\ x &= 8 + 15(4 + 7c) \\ &\text{and so on...} \end{align}

• Could you explain how you went from "3a is congruent to 1 mod 5" to "a is congruent to 2 mod 5", and "8 + 1b is congruent to 5 mod 7" to "1 + b is congruent to 5 mod 7"? Other than that I understand how to solve it. Jun 5 '16 at 3:56
• @EriqueB. : Trial and error. I looked at $3a \equiv 1 \pmod 5$ and thought of $3a = 6$. $8 + 1b \pmod 7 \equiv 1 + b \pmod 7$ since $8 \equiv 1 \pmod 7$. Sep 12 '16 at 3:31

Both mod 3 and mod 11 had the form $$x≡ -4$$. Combine both:
$$x≡ -4 \text{ (mod 33)}$$ The rest (mod 5, 7, 13) had the form $$x≡ -2$$. Combine the rest:
$$x≡ -2 \text{ (mod 455)} → x=455y-2$$ Combine all modulo equations: $$455y-2 ≡ -4 \text{ (mod 33)}$$ $$-7y≡ -2≡ -35 \text{ (mod 33)}$$ $$y≡5 \text{ (mod 33)} → y=33z+5$$ Substitute back to x: $$x= 455(33z+5)-2= 15015z + 2273$$ $$x≡ 2273 \text{ (mod 15015)}$$