1
$\begingroup$

I am stuck in a simultaneous linear congruence problem:

\begin{cases} 3x \equiv 2 \pmod{5} \\[4px] 3x \equiv 4 \pmod{7} \\[4px] 3x \equiv 6 \pmod{11} \end{cases}

Using the Chinese remainder theorem, I started with the 'highest' divisor: $11$. Since $(3, 11) =1$ there is a unique solution. $x= 6 \cdot 3 ^{\phi (11) -1} \equiv 6 \cdot 3^4\pmod{11}$ But to be honest, I have no clue how to continue. Perhaps, cancel out the last equation to: $x \equiv 2 \pmod{11}$?

$\endgroup$
2
  • $\begingroup$ Read the Chinese remainder theorem again. There is a unique solution mod 11*3=33 to your last two congruences simultaneously. Then you reduced the problem two find the solution to two simultaneous congruences. Finish by using the CRT again. $\endgroup$
    – mlainz
    Feb 13, 2019 at 20:51
  • $\begingroup$ Would it be correct to say: that the last one $x \equiv 2$ $\mod (11)$ has solutions: $13, 24, 35...$ The equation $3x \equiv 4$ $mod (7)$ has solutions: $13, 20, 27...$ And finally the first one has solutions: $9, 14, 19 ...$. So the simultaneous solution is $x=244$ $\endgroup$
    – mathpieuler
    Feb 13, 2019 at 22:28

3 Answers 3

Reset to default
4
$\begingroup$

First, you could observe that

\begin{cases} 3x \equiv 2 \pmod{5} \Leftrightarrow 3x \equiv 2+10 \equiv 12=3 \cdot 4 \pmod{5} \Leftrightarrow x \equiv \color{red}{4} \pmod{5} \\[4px] 3x \equiv 4 \pmod{7} \Leftrightarrow 3x \equiv 4+14 \equiv 18=3 \cdot 6\pmod{7} \Leftrightarrow x \equiv \color{lime}{6} \pmod{6} \\[4px] 3x \equiv 6 \pmod{11} \Leftrightarrow x \equiv \color{blue}{2} \pmod{11} \\[4px] \end{cases}

Next, you could find integers $a, b, c$ with

\begin{cases} a \cdot 7 \cdot 11 \equiv 1 \pmod{5} \Leftrightarrow 2a \equiv 1 \pmod{5} \Leftrightarrow a \equiv 3 \pmod{5}\\[4px] b \cdot 5 \cdot 11 \equiv 1 \pmod{7} \Leftrightarrow 6b \equiv 1 \pmod{7} \Leftrightarrow b \equiv 6 \pmod{7} \\[4px] c \cdot 5 \cdot 7 \equiv 1 \pmod{11} \Leftrightarrow 2c \equiv 1 \pmod{11} \Leftrightarrow c \equiv 6 \pmod{11} \\[4px] \end{cases}

Then, all solutions of your simultaneous congruences are $$x \equiv a \cdot 7 \cdot 11 \cdot \color{red}{4} + b \cdot 5 \cdot 11 \cdot \color{lime}{6} + c \cdot 5 \cdot 7 \cdot \color{blue}{2} \pmod{5 \cdot 7 \cdot 11}$$ so $x \equiv 244 \pmod{385}$.

Btw: Did anybody notice that this way of constructing a solution is exactly the same as finding an interpolation polynomial using Lagrange polynomials?

$\endgroup$
2
  • 1
    $\begingroup$ You could view the polynomial interpolation problem as being a version of a Chinese Remainder Theorem problem, just in the ring $\mathbb{R}[x]$ instead of in the ring $\mathbb{Z}$. e.g. solving $p(a_1) = b_1$, $\ldots$, $p(a_n) = b_n$ is equivalent to solving $p(x) \equiv b_1 \pmod{x - a_1}$, $p(x) \equiv b_2 \pmod{x - a_2}$, $\ldots$, $p(x) \equiv b_n \pmod{x - a_n}$. $\endgroup$
    – Daniel Schepler
    Feb 14, 2019 at 0:33
  • 1
    $\begingroup$ @DanielSchepler Very nice, thank you! On the other hand, one can also apply other techniques for finding interpolation polynimia to the simultaneous congruences problem. In fact, more that 30 yeas ago, I applied the method of divided differences to simultaneous congruences to receive a solution in the "Newton form": $$x \equiv c_1+b_1\left(c_2+b_2\left(c_3+...+b_{n-1}\left(c_{n}\right)...\right)\right) \pmod{b_1\cdot...\cdot b_n}$$ I recall that for the "dividing" I used Euklid's algorithm. $\endgroup$
    – Wolfgang Kais
    Feb 14, 2019 at 9:14
2
$\begingroup$

It just jumped out at me that if I define $y=x+1$ the first two become $$3y \equiv 0 \pmod 5\\3y \equiv 0 \pmod 7$$ which clearly calls for $y$ to be a multiple of $35$. Now we have $$3y \equiv 9 \pmod {11}\\y \equiv 3 \pmod {11}$$ We note that $35 \equiv 2 \pmod {11}$ so $7 \cdot 35 = 245 \equiv 7\cdot 2 \equiv 14\equiv 3 \pmod{11}$ and $y=245, x=244$ is a solution.

$\endgroup$
1
$\begingroup$

This is an old-fashioned solution.

$$3x \equiv 2 \mod 5 \qquad 3x \equiv 4 \mod 7 \qquad 3x \equiv 6 \mod{11}$$

\begin{array}{|r|rrr|} \hline 385 & 5 & 7 & 11 \\ \hline 77 & 2 & 0 & 0 \\ 55 & 0 & 6 & 0 \\ 35 & 0 & 0 & 2 \\ \hline 231 & 1 & 0 & 0 \\ -55 & 0 & 1 & 0 \\ -175 & 0 & 0 & 1 \\ \hline \end{array}

$$3x \equiv 2(231) -4(55) -6(175) \equiv -808 + 385^{\#} \equiv -423 \pmod {385}$$

$$x \equiv -141 \equiv 244 \pmod {385}$$

($\#:$ Adding $385$ makes the answer, $-423$, a multiple of $3$.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .