Results 1 to 2 of 2

Math Help - Chinese remainder theorem 2

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

    Chinese remainder theorem 2

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

    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
    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: June 21st 2011, 07:47 AM
  2. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 15th 2008, 07:12 PM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 9th 2008, 01:32 AM
  4. Chinese Remainder Theorem 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 26th 2007, 09:00 PM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2006, 08:28 AM

Search Tags


/mathhelpforum @mathhelpforum