Solving congruences I've the following congruence system:
\begin{align*}
I \quad 2x \equiv 0\mod 7 \\
II \quad x \equiv 1 \mod 5\\
III \quad x \equiv 3 \mod 4 
\end{align*}
Now I tried to solve it:
\begin{align*}
II \quad &x \equiv 1 \mod 5 \Rightarrow x=5x_1+1\\
\stackrel{I}{\Rightarrow} 2(5x_1+1) &\equiv 0 \mod 7 \\
\Leftrightarrow 10x_1+2 &\equiv 0 \mod \\
\Leftrightarrow 10x_1 &\equiv -2 \mod 7\\
\Leftrightarrow 10x_1 &\equiv 12 \mod 7\\
\Rightarrow 5x_1 &\equiv 6 \mod 7 \Rightarrow 5x_1=7x_2+6
\end{align*}
and now
$$x=5x_1+1=7x_2+6+1=7x_2+7 \Leftrightarrow x \equiv 0 \mod 7$$
This result is obviously no solution. If I try to solve it with euclidean algorithm, I'll get the correct result. Now I try to unterstand why the first idea is wrong. In general I understood the way of solving congruence systems, but never thought about why it works.
Any help is appreciated.
 A: It's a good idea to try a pedestrian way to solve your problem.
Here's mine.
Let $x\in\mathbb{Z}$ be a solution of your system. Then
there exists $a,b,c\in\mathbb{Z}$ such that:
$$\begin{cases}2x=7a\\x=1+5b\\x=3+4c.\end{cases}$$
We must then have1:
$$\begin{cases}40x=140a\\28x=28+140b\\35x=105+140c\end{cases}$$
Now2, $3\times40-3\times28-35=1$, hence:
$$x=-3\times28-105+140(3a-3b-c)=-189+140(3a-3b-c),$$
i.e.,
$$x=91+140(3a-3b-c-2).$$
Hence a necessary condition for $x\in\mathbb{Z}$ to be a solution of your system is:
$$x=91\mod 140.$$
It is now easy to check that this condition is also sufficient: let $m\in\mathbb{Z}$ and set $x=91+140m$. Then:
$$x=7\times(13+20m)$$
hence $x=0\mod 7$.
$$x=1+5\times(18+28m)$$
hence $x=1\mod 5$.
$$x=3+4\times(22+45m)$$
hence $x=3\mod 4$.


In general I understood the way of solving congruence systems, but never thought about why it works.

Hope this helps…

1$140$ naturally appears as the least common multiple of $4$, $5$ and $7$.
2We're lucky to find such a simple relation, aren't we?
A: $$2x\equiv0\pmod7\iff x\equiv0\pmod7,x\equiv1\pmod5,x\equiv3\pmod4$$
As $7,5,4$ are pairwise relatively prime, we can safely apply CRT

Otherwise,  $x\equiv0\pmod7\implies x=7x_1, x\equiv1\pmod5\implies x=5x_2+1$
So, we have $7x_1=5x_2+1\iff 7x_1-5x_2=1$
Applying the convergence property of continued fraction $\displaystyle\frac75=1+\frac25=1+\frac1{\dfrac52}=1+\frac1{1+\dfrac12}$, $\displaystyle 7\cdot2-5\cdot3=-1\implies 7x_1-5x_2=5\cdot3-7\cdot2$
$\displaystyle\iff7(x_1+2)=5(x_2+3)\iff \frac{7(x_1+2)}5=x_2+3$ which is an integer
$\displaystyle\implies5|7(x_1+2)\iff 5|(x_1+2)$ as $5\nmid 7$
$\displaystyle\implies x_1+2=5x_3\iff x=7x_1=7(5x_3-2)$
Can you take it from here?
A: Solving the first and second equations simultaneously, you get x = 21 mod 35. Solving the second and third equations simultaneously, you get x = 11 mod 20.
Solving these two results simultaneously, you get x = 91 mod 140 which gives you all possible solutions.
