0
$\begingroup$

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.

Thanks for your help!

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So the problem is not solvable using CRT? $\endgroup$ – juper Oct 14 '17 at 21:42
  • $\begingroup$ 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 ? $\endgroup$ – Junkyards Oct 14 '17 at 21:45
  • $\begingroup$ 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 $\endgroup$ – juper Oct 14 '17 at 22:08
  • $\begingroup$ 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$. $\endgroup$ – Junkyards Oct 14 '17 at 22:11
  • $\begingroup$ 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. $\endgroup$ – juper Oct 14 '17 at 22:44
0
$\begingroup$

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

$\endgroup$

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.