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

  • $\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 '19 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 '19 at 22:28

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?

  • $\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 '19 at 0:33
  • $\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 '19 at 9:14

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.


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.