5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ You should not write $5x_1 = 7x_2 + 6$. Instead, continue solving $5x_1 \equiv 6 \pmod{7}$ for $x_1$, and then write $x_1 = 7x_2 + a$. Then you get $x = 5(7x_2+a)+1 = 35x_2 + (5a+1)$. Then tackle the next congruence. $\endgroup$ – Daniel Fischer Jun 28 '14 at 11:57
  • 2
    $\begingroup$ I'm not sure why you conclude that the result is obviously no solution. $\endgroup$ – Joe Johnson 126 Jun 28 '14 at 12:01
  • $\begingroup$ @JoeJohnson126 because 7 is not equivalent to 1 mod 5 (congruence II) $\endgroup$ – ulead86 Jul 6 '14 at 18:32
2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Thanks, with necessary/sufficient it seems quite logical. Thanks a lot. $\endgroup$ – ulead86 Jul 6 '14 at 18:30
1
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Did the OP not say that knows how to solve it using Euclidean algorithm, and was only interested in learning what is wrong with his other approach? $\endgroup$ – Jyrki Lahtonen Jun 28 '14 at 12:00
  • 1
    $\begingroup$ @JyrkiLahtonen, I've demonstrated the existence of the solution $\endgroup$ – lab bhattacharjee Jun 28 '14 at 12:05
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.