Chinese remainder theorem 2

**oldguynewstudent** · November 19th 2009, 07:35 AM

Find all solutions, if any, to the system of congruences
x $\equiv$ 7 (mod 9)
x $\equiv$ 4 (mod 12)
x $\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 $\equiv$ 4 (mod 12), we must have x $\equiv$ 4 $\equiv$ 1 (mod 3) and x $\equiv$ 4 $\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 $\equiv$ 1 (mod 3) and x $\equiv$ 2 (mod 7). Why?

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

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

Thanks for any explanations.

**clic-clac** · November 19th 2009, 10:38 AM

That's the application of the CRT:

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

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

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

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

Thread: Chinese remainder theorem 2

LinkBack

Thread Tools

Display

Chinese remainder theorem 2

Similar Math Help Forum Discussions

Chinese remainder theorem

Chinese remainder theorem

Chinese Remainder Theorem

Chinese Remainder Theorem 1

Chinese Remainder Theorem

Search Tags