Simultaneous congruences $3x \equiv 2 \pmod{5}$, $3x \equiv 4 \pmod{7}$, $3x \equiv 6 \pmod{11}$

Question

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

Answer 1

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?

Answer 2

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.

Answer 3

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$.)