# 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.

• @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$. – steven gregory 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)}$$