# Chinese Remainder Theorem problem 7

I have been set the task of solving the following set of congruences using CRT.

\begin{align} x&=2\mod 11, \\ x&=3 \mod 12, \\x&=4 \mod 15.\end{align}

I solved the equation of $M_1 = 12 \times 15 = 180$ and then $1 \equiv 180x \mod 11$ to get $x=3$.

My next equation to solve would be $M_2 = 11 \times 15 =165$ and then $1 \equiv 165x \mod 12$ however this cannot be solved so I'm wondering where I have gone wrong.

This is my second time attempting a CRT question after being shown the method above in my lecture however I cannot seem to see what I am doing wrong.

I did not go into details about the computation, but just notice that $12$ and $15$ have a common factor $3$. So in some cases there will not be any solutions (the CRT does not apply here).

• So the problem is not solvable using CRT? – juper Oct 14 '17 at 21:42
• It all depends on the system. Either there is a solution and you can "simplify" you equation into a form where your numbers will be relatively primes ; or you can prove there is no solution. In this case, suppose that $x$ exists. Then there exist $k,k'$ such that $x = 3 + 12k = 4 + 15k'$. Can you see why it is not possible ? – Junkyards Oct 14 '17 at 21:45
• Well I have tried to work out your statement and arrived at x=15 and x=4 which is incorrect (I think I did the correct workings out) so it is not possible? this whole CRT is very new to me – juper Oct 14 '17 at 22:08
• How did you obtain that ? You were just supposed to get $1 = 12k - 15k' = 3(4k - 5k')$, which is a contradiction because $1$ is not a multiple of $3$. – Junkyards Oct 14 '17 at 22:11
• Yes I also got that, I have no idea what I was doing when I typed before. I forgot that the numbers had to be integers - silly mistake of mine. This makes perfect sense so that you very much for your help. – juper Oct 14 '17 at 22:44

You have

\begin{align} x &\equiv 2 \mod{11} \\ x &\equiv 3 \mod{12} \\ x &\equiv 4 \mod{15} \end{align}

and we notice that $12$ and $15$ are not relatively prime. This does not immediately prove that you cannot use the CRT. What you have to do is restate the congruences in terms or prime-power factors.

$\begin{array}{l} x & \equiv &2 \mod{11} &\implies \left\{ \begin{array}{l} x & \equiv &2 \mod{11} \\ \end{array} \right. \\ x & \equiv &3 \mod{12} &\implies \left\{ \begin{array}{l} x & \equiv &0 \mod{3}\\ x & \equiv &3 \mod{4}\\ \end{array} \right. \\ x & \equiv &4 \mod{15} &\implies \left\{ \begin{array}{l} x & \equiv &1 \mod{3}\\ x & \equiv &4 \mod{5}\\ \end{array} \right. \\ \end{array}$

You cannot solve this problem because you cannot solve $x \equiv 0 \pmod 3$ and $x \equiv 1 \pmod 3$ simultaneously.

In general, a system $$\{ x \equiv a_i \pmod{m_i} \}_{i=1}^N$$

can be solved using the Chinese Remainder Theorem if and only if, for every $(i,j)$ pair we have $a_i \equiv a_j \mod{\gcd(m_i,m_j)}$.

So the above system of congruences can't be solved because $3 \not \equiv 4 \mod{\gcd(12,15)}$.

Here is an example of a system that has a solution.

If you had started with the system of congruences

\begin{align} x &\equiv 2 \mod{11} \\ x &\equiv 3 \mod{12} \\ x &\equiv 6 \mod{15} \end{align}

Then the prime-power congruences would have been $\begin{array}{l} x & \equiv &2 \mod{11} &\implies \left\{ \begin{array}{l} x & \equiv &2 \mod{11} \\ \end{array} \right. \\ x & \equiv &3 \mod{12} &\implies \left\{ \begin{array}{l} x & \equiv &0 \mod{3}\\ x & \equiv &3 \mod{4}\\ \end{array} \right. \\ x & \equiv &4 \mod{15} &\implies \left\{ \begin{array}{l} x & \equiv &0 \mod{3}\\ x & \equiv &1 \mod{5}\\ \end{array} \right. \\ \end{array}$

Which can be "simplified" to

\begin{align} x &\equiv 0 \mod{3} \\ x &\equiv 3 \mod{4} \\ x &\equiv 1 \mod{5} \\ x &\equiv 2 \mod{11} \end{align}

You get $M = 660$,

$M_1=220\equiv 1 \pmod 3, \quad M_1^{-1} \equiv 1 \pmod 3, \quad 220 \times 1 = 220$

$M_2=165 \equiv 1 \pmod 4, \quad M_2^{-1} \equiv 1 \pmod 4, \quad 165 \times 1 = 165$

$M_3=132 \equiv 2 \pmod 5, \quad M_3^{-1} \equiv -2 \pmod 5, \quad 132 \times -2 = -264$

$M_4= 60 \equiv 5 \pmod{11}, \quad M_4^{-1} \equiv -2 \pmod{11}, \quad 60 \times -2 = -120$

So $x \equiv 0(220) + 3(165) + 1(-264) + 2(-120) \equiv -9 \equiv 651 \pmod{660}$