# Chinese Remainder Theorem When GCD is not 1

I've got this system of equations that I'm trying to solve. I'm pretty sure I have to use the CRT, but to my understanding, it can only be used when GCD of all the mods is 1. I don't want an answer because this is a homework problem. I just have a question. The system is $$x \equiv 1 \mod 2$$ $$x \equiv 2 \mod 3$$ $$x \equiv 3 \mod 4$$ $$x \equiv 4 \mod 5$$ $$x \equiv 5 \mod 6$$ $$x \equiv 0 \mod 7$$

gcd(2,4) $\ne$ 1, gcd(3,6) $\ne$ 1, gcd(2,6) $\ne$ 1, gcd(4,6) $\ne$ 1. So I can't use the Chinese Remainder Theorem here. My question is, can I simplify it as follows

• If I list out the first congruence class of mod 2, then the numbers are all either 1 or 3 mod 4
• If I list out the second congruence class of mod 3, then the numbers are all either 2 or 5 mod 6.

With the above observations, I simplify the system to $$x \equiv 3 \mod 4$$ $$x \equiv 4 \mod 5$$ $$x \equiv 5 \mod 6$$ $$x \equiv 0 \mod 7$$

Now I observe that when I write out the thrid congruence class in mod 4, then numbers are all either 3, 1, or 5 mod 6. So I simplify the above to $$x \equiv 4 \mod 5$$ $$x \equiv 5 \mod 6$$ $$x \equiv 0 \mod 7$$

Can I simplify the system to the above three equations?

Any help would be appreciated Thanks

Note that if $x \equiv 3 \pmod 4$ then necessarily $x \equiv 1 \pmod 2$. Simiarly, if $x \equiv 5 \pmod 6$ then $x \equiv 2 \pmod 3$. So you can actually remove the equations $x \equiv 1\pmod 2$ and $x \equiv 2 \pmod 3$ because they are implied by the other equations.

Now $4$ and $6$ are still not coprime. You should be able to show that $x \equiv 3 \mod 4$ and $x \equiv 5 \mod 6$ if and only if $x \equiv 11 \pmod {12}$. So those two equations can be replaced by the one equation $x \equiv 11 \pmod {12}$. Now you only have three equations, and $\gcd(12,5,7)=1$, so you can apply the Chinese remainder theorem.

• Thanks for that. I just tried out my method as well as yours and they both give the same answer. Is my method correct as well, or would it not work in other cases? Jun 3, 2016 at 3:10
• I don't understand what you mean by "Now I observe that when I write out the thrid congruence class in mod 4, then numbers are all either 3, 1, or 5 mod 6." The three equations you are left with do not give a correct answer. By my calculations, they give $x\equiv 119 \pmod {210}$. Yet $x=329$ satisfies this but not $x \equiv 3\pmod {4}$.
– kccu
Jun 3, 2016 at 17:00
• The only time you can get rid of an equation is if it is implied by the other equations, e.g. $x \equiv 3 \pmod 4 \Rightarrow x \equiv 1 \pmod 2$. In my answer I combined two equations into one, which is okay because they are equivalent: $$x \equiv 3 \pmod 4 \text{ and } x \equiv 5 \pmod 6 \Leftrightarrow x \equiv 11 \pmod {12}.$$ You removed the equation $x\equiv 3 \pmod 4$, but this equation is not implied by the others, as I showed with the example $x =329$.
– kccu
Jun 3, 2016 at 17:02

A shortcut first. Note that

$$x \equiv 1 \mod 2$$ $$x \equiv 2 \mod 3$$ $$x \equiv 3 \mod 4$$ $$x \equiv 4 \mod 5$$ $$x \equiv 5 \mod 6$$

is equivalent to

$$x \equiv -1 \mod 2$$ $$x \equiv -1 \mod 3$$ $$x \equiv -1 \mod 4$$ $$x \equiv -1 \mod 5$$ $$x \equiv -1 \mod 6$$

which is equivalent to

$$x \equiv -1 \mod 60$$

where $60 = \operatorname{lcm(2,3,4,5,6)}$$Then you only need to solve$$x \equiv -1 \mod 60x \equiv 0 \mod 7$$In more general cases, I find it easiest to decompose each equivalence into equivalent prime-power equivalences. It sucks up a bit more space but makes it easier to find what is essential. Note x \equiv 3 \mod 4 implies x \equiv 1 \mod 2. So we can remove x \equiv 1 \mod 2. Note x \equiv 5 \mod 6 implies \begin{array}{l} x \equiv 1 \mod 2 \\ x \equiv 2 \mod 3 \\ \end{array} We have already removed x \equiv 1 \mod 2. So, if we leave x \equiv 2 \mod 3, then we can remove x \equiv 5 \mod 6, which is the more complicated congruence.$$\color{red}{x \equiv 1 \mod 2}x \equiv 2 \mod 3x \equiv 3 \mod 4x \equiv 4 \mod 5\color{red}{x \equiv 5 \mod 6}x \equiv 0 \mod 7$\$

Note that the remaining congruences are amenable to the CRT.