I am unable to use the Chinese Remainder Theorem when the modulus is not coprime. I want to solve the following:

$$ x \equiv 5 \text{ (mod 6)}\\ x \equiv 7\text{ (mod 15)} $$ I tried breaking the system as:

$$ x\equiv5\text{ (mod 2)}\\ x\equiv5\text{ (mod 3)}\\ x\equiv7\text{ (mod 3)}\\x\equiv7\text{ (mod 5)} $$ and using the values of $x \text{ (mod 3)}$, I got a contradiction, but clearly $x =22$ is a solution. Can you please help me find where I have gone wrong? Thanks.

  • $\begingroup$ Your approach is good; see my answer below $\endgroup$ Mar 1 '20 at 13:03
  • $\begingroup$ So, I guess this system does not have any solution in integers. Am I correct? $\endgroup$
    – Kashif
    Mar 1 '20 at 13:20
  • 1
    $\begingroup$ Yes, you are correct $\endgroup$ Mar 1 '20 at 13:25

$x=22$ is not a solution, since $22\not\equiv5\pmod6$.


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.