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.
 A: \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}
A: 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)}$$
A: 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}
$$
A: 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.
