How to solve the following system using Chinese Remainder Theorem?

$$2·x+1≡0\pmod5\\x+2≡0\pmod7\\5·x+1≡0\pmod9$$ Three equations from the system but I don't know how to solve this kind of (with $+1$ and $2x$ etc.) equation.

Please help me, thank you in advance :)

Solution 1:

$$\begin{equation}\begin{split}2x+1&\equiv 0\mod 5\\2x&\equiv-1\mod 5\\2x&\equiv4\mod 5\\x&\equiv 2\mod 5\\x&=5l+2\end{split}\qquad\begin{split}x+2&\equiv 0\mod 7\\x&\equiv-2\mod7\\x&\equiv5\mod7\\5l+2&\equiv5\mod7\\5l&\equiv 3\mod 7\\5l&\equiv10\mod7\\l&\equiv 2\mod 7\\l&=7m+2\end{split}\qquad\begin{split}5x+1&\equiv 0\mod 9\\5x&\equiv-1\mod9\\5(5l+2)&\equiv-1\mod9\\25l+10&\equiv-1\mod9\\25l&\equiv -11\mod9\\25l&\equiv25\mod9\\l&\equiv 1\mod9\\7m+2&\equiv1\mod9\\7m&\equiv -1\mod9\\7m&\equiv35\mod9\\m&\equiv 5\mod9\\m&=9n+5\end{split}\end{equation}$$

Final answer: $$\begin{align}x&\equiv5l+2\\&\equiv 5(7m+2)+2\\&\equiv5(7(9n+5)+2)+2\\&\equiv5(63n+37)+2\\&\equiv 315n+187\\x&\equiv 187\mod315\end{align}$$

Solution 2:

The basic content of the Chinese remainder theorem is that we can do modular arithmetic with respect to each prime separately. In this case, that means that you can take any step that you would normally take to solve a congruence either at the single-prime level or at the multi-prime level, and the more of them you take at the single-prime level, the easier the calculation becomes.

I’ll do it in two ways, the hard way and the easy way, to demonstrate this.

The hard way is to immediately go to the multi-prime level and solve the equations there. Denote by $(a,b,c)$ the least integer with remainders $a$, $b$ and $c$ with respect to $5$, $7$ and $9$, respectively. Then we have the equation

$$ (2,1,5)x+(1,2,1)\equiv0\mod315\;, $$

which is

$$ 302x+226\equiv0\mod315\;. $$

Taking the $226$ to the right yields

$$ 302x\equiv89\mod315\;. $$

Now we have to find the inverse of $302$, a somewhat non-trivial endeavour. This answer shows how to find the order of $302$ modulo $315$ efficiently (but remember: “There is surely nothing quite so useless as doing with great efficiency what should not be done at all.”). The result is $12$, so the inverse is $302^{11}\equiv218\bmod315$. Then with $218\cdot89\equiv187\bmod315$ we get the final result

$$ x\equiv187\mod315\;. $$

Now, to make your life easier, you can instead solve the congruences at the single-prime level first and only then apply the Chinese remainder theorem to get the final result. Modulo $5$, the additive inverse of $1$ is $4$ and the multiplicative inverse of $2$ is $3$, so the first congruence becomes

$$ 2x\equiv4\mod5 $$

and then

$$ x\equiv3\cdot4\equiv2\mod5\;. $$

Modulo $7$, the additive inverse of $2$ is $5$, so the second congruence becomes

$$ x\equiv5\mod7\;. $$

Modulo $9$, the additive inverse of $1$ is $8$ and the multiplicative inverse of $5$ is $2$, so the third congruence becomes

$$ 5x\equiv8\mod9 $$

and then

$$ x\equiv2\cdot8\equiv7\mod9\;. $$

Now we just need to find $(2,5,7)$, which is $187$, to get the same final result,

$$ x\equiv187\mod315\;. $$

Note that in doing it this way, we were always dealing with single-digit numbers up to the last step.

Solution 3:

$\!\bmod 9\!:\ 5x\equiv -1\!\!\!\overset{\times 2\!\!}\iff\! x\equiv \color{#0a0}{-2}\,\ $ & $\bmod 7\!:\ x\equiv \color{#0a0}{-2}\!\overset{\large \rm\color{#90f}{CCRT}\!\!}\iff \bmod \color{#0a0}{63\!:\ x\equiv -2}$

$\!\bmod\color{#c00} 5\!:\ {-}1\equiv 2x\!\!\!\overset{\times 3\!\!}\iff\! 2\equiv x = \color{#0a0}{-2\!+\!63j}\equiv -2\!+\!3j\!\iff 3j\equiv 4\equiv9\iff \color{#c00}j\equiv \color{#c00}3$

Therefore, we conclude that: $\ \ x = -2\!+\!63\color{#c00}j = -2 + 63(\color{#c00}{3\!+\!5n}) = \bbox[5px,border:1px solid #c00]{187\!+\!315n}$