Solving a linear congruence system

Question

How can this linear congruence system be solved by using Chinese remainder theorem?

\begin{align} 12x&\equiv -7 \pmod {13}\\ 4x&\equiv 7 \pmod {9}\\ 2x&\equiv -3 \pmod {11} \end{align}

As far as I understand, we have to create some M numbers as it follows: \begin{align} M = 13 * 9 * 11 = 1287\\ M_1 = 9 * 11 = 99\\ M_2 = 13 * 11 = 143\\ M_3 = 13 * 9 = 117 \end{align}

But from here forward it becomes confusing for me. What should be done next?

Thank you in advance.

Answer 1

You can start by simplifying each of the given equations into the form $x\equiv k_i \bmod m_i$.

For example, $4x \equiv 7 \equiv 16 \implies x\equiv 4 \bmod 9$

Then the generalized solution to the Chinese remainder theorem becomes more accessible.

However it's often at least as efficient to construct the answer by combining $2$ modulus equations at a time to make a resulting single equation, especially if some of the $k_i$ turn out to be the same (as here).

Answer 2

Note that CRT guarantees that an unique solution exist mod $9\cdot 11 \cdot 13$ since those are relatively primes but doesn’t give any particular method to solve the problem others that those used for the proof that you can find here.

To find the solution here we can proceed as follow

• $12x \equiv -7 \iff x\equiv 7 \pmod {13}$
• $4x\equiv 7 \iff x\equiv 4 \pmod {9}$
• $2x\equiv -3 \iff x\equiv 4 \pmod {11}$

this is the standard form for the system , then

• $x\equiv 7 \pmod {13}\implies x=7+13k$
• $x\equiv 4\implies 7+4k\equiv 4\implies 4k\equiv 6 \implies k\equiv 6 \pmod {9}\implies x=7+13(6+9h)=85+9\cdot13h$
• $x\equiv 4 \implies 8+7h\equiv4 \implies h\equiv 1 \pmod {11} \implies x=85+9\cdot13(1+11s)=202+9\cdot11\cdot 13s$

that is $$x=202 \pmod{9\cdot11\cdot 13}$$

Answer 3

Solve the first congruence:

$$12x \equiv -7 \pmod{13} \implies x \equiv 7 \pmod{13}$$

So now we know $x = 13t+7$ for some integer $t$.

Substitute into the second congruence: $$ 4(13t+7)\equiv 7\pmod 9 $$ Solve this and you'll find that $t\equiv c \pmod 9$ for some constant $c$. Then you'll know that $t = 9s +c$ for some integer $s$. Substitute this into the expression for $x$ above, and you'll have $x=9\cdot 13s + k$ for some integer $k$. Substitute this into the third congruence and solve for $s$ modulo 11. Finally, you'll get an expression for $x$ modulo $13 \cdot 9 \cdot 11$