Chinese Remainder Theorem When GCD is not 1

Question

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

Answer 1

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.

Answer 2

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

$$x \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 3$$ $$x \equiv 3 \mod 4$$ $$x \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.