<s>[INST] 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.
 [/INST] I shall solve the system of modulo equations by Chinese Remainder Theorem. I firstly solve the following system:
$$
\left\{\begin{array}{ll}
5 \times 7 \times 11 \times 13 A \equiv 2 & (\bmod 3) \\
3 \times 7 \times 11 \times 13 B \equiv 3 & (\bmod 5) \\
3 \times 5 \times 11 \times 13 C \equiv 5 & (\bmod 7) \\
3 \times 5 \times 7 \times 13 D \equiv 7 & (\bmod 11) \\
3 \times 5 \times 7 \times 11 E \equiv 11 & (\bmod 13)
\end{array}\right.
\iff \left\{\begin{aligned}
A & \equiv 2 \quad (\bmod 3) \\
3 B & \equiv 3 \quad (\bmod 5) \\
-4 C & \equiv 5 \quad (\bmod 7) \\
D & \equiv 7 \quad (\bmod 11) \\
11E & \equiv 11 \quad(\bmod 13)
\end{aligned}\right.
$$
$$
\iff\left\{\begin{array}{l}
A \equiv 2 \quad (\bmod 3) \\
B \equiv 1 \quad (\bmod 5) \\
C \equiv 4 \quad (\bmod 7) \\
D \equiv 7 \quad (\bmod 11) \\
E \equiv 1 \quad (\bmod 13)
\end{array}\right.
$$
By the Chinese Remainder Theorem, the general solution is
$$
\begin{aligned}
x \equiv & 5005 \times 2+3003 \times 1+2145 \times 4 +1365 \times 7+1155 \times 1 \quad(\bmod 15015) \\
\equiv & 2273 \quad(\bmod 15015)
\end{aligned}
$$
</s>