Results 1 to 2 of 2

Math Help - Chinese Remainder Theorem

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    79

    Chinese Remainder Theorem

    I understand how to do the Chinese Remainder Theorem when all of the moduli are pairwise relatively prime, but I don't understand how to do it when all of the moduli are NOT pairwise relatively prime.

    For example, say we have
    x≡9 (mod 12)
    x≡3 (mod 9)
    x≡7 (mod 10)

    According to my teacher this becomes
    x≡1 (mod 4)
    x≡3 (mod 9)
    x≡2 (mod 5).
    I don't understand how this was arrived at though. Could someone please clearly explain the process?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    x≡9 (mod 12)
    x≡3 (mod 9)
    x≡7 (mod 10)

    x≡1 (mod 4)
    x≡3 (mod 9)
    x≡2 (mod 5)

    Uhm, Chinese Remainder Theorem just ensure you there exist an x such that all those conditions are satisfied.

    Well, you know that x≡9 (mod 12), then x-9=M_{12} \Rightarrow x-9=M_4 and x-9=M_3 (both are true).
    x-9=M_4 \Rightarrow x-1=M_4+8=M_4 \Rightarrow x≡1 (mod 4).

    x≡3 (mod 9) Remained unchanged.

    x≡7 (mod 10), then x-7=M_{10} \Rightarrow x+3=M_{10} \Rightarrow x+3=M_2 and x+3=M_5 (both are true).
    x+3=M_5 \Rightarrow x-2=M_5-5=M_5 \Rightarrow x≡2 (mod 5).

    I considered M_k=\left \{ mk| m\in \mathbb{Z} \right \}, k \in \mathbb{N}. (set of multiples of a number)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The chinese remainder theorem.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 12th 2011, 07:52 PM
  2. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 22nd 2009, 05:00 PM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 9th 2008, 12:32 AM
  4. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 29th 2008, 02:20 PM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2006, 07:28 AM

Search Tags


/mathhelpforum @mathhelpforum