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
 A: 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.
A: 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.
