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.