# Thread: Chinese remainder theorem 2

1. ## Chinese remainder theorem 2

Find all solutions, if any, to the system of congruences
x $\displaystyle \equiv$ 7 (mod 9)
x $\displaystyle \equiv$ 4 (mod 12)
x $\displaystyle \equiv$ 16 (mod 21)

Solution manual states: We cannot apply the CRT directly, since the moduli are not pairwise relatively prime. (Got that on my own.) However, we can, using the CRT, translate these congruences into a set of congruences that together are equivalent to the given congruence. Since, we want x $\displaystyle \equiv$ 4 (mod 12), we must have x $\displaystyle \equiv$ 4 $\displaystyle \equiv$ 1 (mod 3) and x $\displaystyle \equiv$ 4 $\displaystyle \equiv$ 0 (mod 4).

First question, how do we convert congruences? I can see that dividing the 4 and 12 by 4 could give 1 (mod 3), is that the correct procedure? But I don't see how that equates to 0 (mod 4), could you help me there?

Similarly, from the third congruence we must have x $\displaystyle \equiv$ 1 (mod 3) and x $\displaystyle \equiv$ 2 (mod 7). Why?

From here I think I can solve the following system with the excellent help I've received previously.

x $\displaystyle \equiv$ 7 (mod 9)
x $\displaystyle \equiv$ 0 (mod 4)
x $\displaystyle \equiv$ 2 (mod 7).

Thanks for any explanations.

2. That's the application of the CRT:

$\displaystyle 12=3\times 4,$ and $\displaystyle gcd(3,4)=1,$ therefore $\displaystyle (\mathbb{Z}_{12},+)=(\mathbb{Z}_{3\times 4},+)\cong (\mathbb{Z}_3\times\mathbb{Z}_4,+)$

The isomorphism existence (defined by $\displaystyle [x]_{12}\mapsto ([x]_{3},[x]_{4})$) comes from the CRT. (where $\displaystyle [x]_n$ stands for $\displaystyle x\mod n$)

So $\displaystyle (x\equiv 4\mod 12)$ iff $\displaystyle (x\equiv 4\mod 3\ \text{and}\ x\equiv 4\mod 4)$ i.e. iff $\displaystyle (x\equiv 1\mod 3\ \text{and}\ x\equiv 0\mod 4)$

And same thing with $\displaystyle 21=3\times 7$