I have the following system of congruences:
\begin{align*}
x &\equiv 1 \pmod{3} \\
x &\equiv 4 \pmod{5} \\
x &\equiv 6 \pmod{7}
\end{align*}
I tried solving this using the Chinese remainder theorem as follows:
We have that $N = 3 \cdot 5 \cdot 7 = 105$ and $N_1=35, N_2=21, N_3=15$.
From this, we get the following
\begin{align*}
35x_1 &\equiv 1 \pmod{3} \\
21x_2 &\equiv 1 \pmod{5} \\
15x_3 &\equiv 1 \pmod{7}
\end{align*}
and this will result in
\begin{align*}
2x_1 &\equiv 1 \pmod{3} \\
x_2 &\equiv 1 \pmod{5} \\
x_3 &\equiv 1 \pmod{7}
\end{align*}
so from CRT $x =x_1N_1b_1 + x_2N_2b_2 + x_3N_3b_3 = 2 \cdot 35 \cdot3 + 1 \cdot 21 \cdot 5 + 1 \cdot 15 \cdot7 = 420 $.
However $420$ doesn't seem to satisfy the given system, what would be the problem here?
Best Answer
From the Chinese remainder theorem:
$$x = x_1N_1b_1 + x_2N_2b_2 + x_3N_3b_3$$ $$= 2 \cdot 35 \cdot \color{red}{1} + 1 \cdot 21 \cdot \color{red}{4} + 1 \cdot 15 \cdot \color{red}{6} = 244$$
The general solution is when $x \equiv 244 \pmod {\text{lcm}(3,5,7)} \Rightarrow x \equiv 244 \pmod {105} \equiv 34 \pmod {105}$, or when $x = 105k + 34$ when $k$ is an integer.
This problem is the exact problem that appears in the Brilliant article on the Chinese remainder theorem. Their method involves rewriting the largest congruence, $x \equiv 6 \pmod 7$ in the form $7j+6$, then substituting the expression into the next largest congruence, so that $7j + 6 \equiv 4 \pmod 5$. Solving this congruence gives $j \equiv 4 \pmod 5$. Repeating this process gives $j = 5k +4$, and substituting into the equation for $j$ gives $x = 7(5k + 4) + 6 = 35k + 34$. $35k + 34 \equiv 1 \pmod 3$ results in $k \equiv 0 \pmod 3$. Therefore $k = 3l$ and $x = 35(3l) + 34$, so $x$ is in the form $105k + 34$.