Solving congruences

Question

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 1

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?

Answer 2

$$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?

Answer 3

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.