Results 1 to 2 of 2

Thread: Chinese remainder theorem 2

  1. #1
    Senior Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    255

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Jun 21st 2011, 06:47 AM
  2. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Dec 15th 2008, 06:12 PM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 9th 2008, 12:32 AM
  4. Chinese Remainder Theorem 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 26th 2007, 08:00 PM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 10th 2006, 07:28 AM

Search Tags


/mathhelpforum @mathhelpforum