Results 1 to 2 of 2

Math Help - Chinese Remainder Theorem

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    42

    Chinese Remainder Theorem

    Suppose (a,b) = 1. As x runs through a complete residue system (mod b) and y runs through a complete residue system (mod a), then ax + by runs through a complete residue system (mod ab).

    I'm curious as to whether this is true. I've tried many examples but have failed to prove the above statement. Any help would be great. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Suppose ax_0+by_0 \equiv ax_1+by_1 \mod ab. We want to show that x_0\equiv x_1 \mod b and y_0 \equiv y_1 \mod a. We have a(x_0-x_1)+b(y_0-y_1)\equiv 0 \mod ab. Reducing \mod a, we have a(x_0-x_1)+b(y_0-y_1) \equiv b(y_0-y_1) \equiv 0 \mod a. Since (a,b)=1, this implies y_0-y_1 \equiv 0 \mod a. The other part follows similarily.
    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: December 28th 2011, 08:53 AM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 6th 2008, 06:07 AM
  3. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2008, 01:27 AM
  4. Chinese Remainder Theorem 3
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 27th 2007, 11:27 AM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2006, 07:28 AM

Search Tags


/mathhelpforum @mathhelpforum