Results 1 to 2 of 2

Math Help - Generalization of the Chinese Remainder Theorem

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    2

    Generalization of the Chinese Remainder Theorem

    Prove the following generalisation of the Chinese Remainder Theorem. Show
    that if
    m1;m2;m3 are pairwise coprime integers and a1 inZ/m1, a2 inZ/m2,

    a
    3 inZ/m3 then there is a unique x inZ/(m1m2m3) such that

    x =a1 mod m1; x =a2 mod m2; x =a3 mod m3:

    Confused!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Do you mean the following (this is the general Chinese remainder theorem):

    Let a_1 \in \mathbb{Z}_{n_1} , a_2 \in \mathbb{Z}_{n_2}, ... , a_k \in \mathbb{Z}_{n_k} where \gcd(n_i,n_j) = 1 \mbox{ for }i\not = j. Then there exists a unique x \in \mathbb{Z}_{n_1...n_k} so that x\equiv a_i (\bmod n_i) for all 1\leq i \leq n.

    Here are the steps:
    1)Define n = n_1...n_k.
    2)Define m_r = n/n_r, i.e. m_r = n_1...n_{r-1}n_{r+1}...n_k.
    3)Prove that \gcd(n_i,m_i) = 1.
    4)Therefore (use #3) the m_ix = 1 has unique solution in \mathbb{Z}_{n_i}.
    5)Denote solution in #4 by x_i.
    6)Define \bold{x} = a_1x_im_1 + ... + a_kx_km_k.
    7)Prove that \bold{x} solves x=a_i for each \mathbb{Z}_{n_i}.
    8)Now prove that there can be no other solution.
    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, 08:52 PM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2010, 08:56 PM
  3. Chinese remainder theorem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 20th 2009, 01:57 PM
  4. CRT(chinese remainder theorem)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 19th 2009, 10:01 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