<s>[INST] 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?
 [/INST] 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}$.
</s>