elementary number theory - 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.

Answer

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 have¹:
$$\begin{cases}40x=140a\\28x=28+140b\\35x=105+140c\end{cases}$$
Now², $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…

---

¹$140$ naturally appears as the least common multiple of $4$, $5$ and $7$.

²We're lucky to find such a simple relation, aren't we?