# Using Chinese Remainder Theorem when the moduli are not mutually coprime.

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.

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

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