System of congurences and the Chinese Remainder Theorem 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?
 A: 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$.
A: Here's how I would do it: using Bezout coefficients, we get $2\cdot5-3\cdot3=1$.  So the solution to $\begin{cases}x\cong1\pmod3\\x\cong4\pmod5\end{cases}$ is $x=1\cdot{10}-4\cdot9=-26\pmod{15}=4\pmod{15}$.
Next we solve $\begin{cases} x\cong{4}\pmod{15}\\x\cong6\pmod7\end{cases}$.
Since $-6\cdot15+13\cdot7=1$, we get $x=6\cdot{-90}+4\cdot91=-540+364=-176\pmod{105}=34\pmod{105}$.
Hence $x\cong 34\pmod{105}$.
A: Here's how I would solve this particular system.
$  x \equiv 4 \pmod{5}$ and $x \equiv 6 \pmod{7}$ means $x\equiv-1\pmod5$ and $x\equiv-1\pmod7$,
which means $x\equiv-1\pmod{35}$, i.e.,  $x\equiv34\pmod{35}$,
which means $x\equiv34, 69$, or $104\pmod{105}$.
By the Chinese remainder theorem, only one of these satisfies   $x\equiv1\pmod3$.
