<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] We have x= 2 (mod 3) and x= 4 (mod 5).
From the first x= 2+ 3i for some integer i.
From the second x= 4+ 5j for some integer j.
2+ 3i= 4+ 5j so 3i- 5j= 2.
Now use the "Chinese remainder theorem to solve that 'Diophantine equation'.
3 divides into 5 once with remainder 2: 5- 3= 2
2 divides into 3 once with remainder 1: 3- 2= 1
3- 2= 3- (5- 3)= 2(3)- 5= 1.
Multiply by 2: 4(3)- 2(5)= 2.
So i= 4+ 5m and j= 2+ 3m for any integer m:
3(4+ 5m)- 5(2+ 3m)= 12+ 15m- 10- 15m= 2.
x= 2+ 3i so x= 2+ 3(4+ 5m)= 14+ 15m.
Now add "x= 5 (mod 7)" which means x= 5+ 7n for some integer n.
x= 14+ 15m= 5+ 7n so 7n- 15m= 14- 5= 9.
7 divides into 15 twice with remainder 1: 15- 2(7)= 1.
Multiply by 9: 9(15)- 18(7)= 9.  n= -18+ 15p and m= -9+ 7p.
If we want positive integer answers, replace p with p+ 2:
n= -18+ 15p+ 30= 12+ 15p and m= -9+ 7p+ 14= 5+ 7p.
We now have x= 5+ 7n= 5+ 7(12+ 15p)= 5+ 84+ 105p= 89+ 105p.
I'll let you finish.
</s>