Solving Chinese Remainder Theorem Algebraically

Question

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.

Answer 1

\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}

Answer 2

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} $$

Answer 3

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.