Results 1 to 4 of 4

Math Help - Chinese Remainder Theorem Help

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Indiana
    Posts
    2

    Chinese Remainder Theorem Help

    This homework is due soon and i can't get this one problem... it's driving me crazy.

    Here it is: Prove and extend or disprove and salvage (with another if and only if statement):
    Statement: Let m and n be two relatively prime integers each greater than 1. Then for integers a and b, the system of simultaneous linear congruences
    ax=b mod m
    ax=b mod n
    (the "=" is supposed to be three lines instead of two, meaning "congruent to")
    has a solution of integer x if and only if there is an integer solution to the linear congruence
    ax=b mod mn
    (again, three lines on the "=")

    You don't have to write out a formal proof for me, just help me understand this and lead me in the right direction so i can write a proof for it. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Chinese Remainder Theorem Help

    To just understand what's going on, maybe look at it this way:
    Let w = ax-b, and then reformulate that statement in terms of n, m, and w.
    Forget about the "has a solution" part, and just see what it's saying about n, m and w.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Indiana
    Posts
    2

    Re: Chinese Remainder Theorem Help

    is it an accurate proof to assume the if and only if statement and then derive the system of linear congruences from the if and only if statement?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Chinese Remainder Theorem Help

    I don't understand that, but I'm pretty sure the answer is no. If you're going to prove something, you need to prove it.
    Think about the lemma below. Can you prove it? How does it relate to the problem?

    Lemma: Suppose n, m and w and integers, and that the gcd(n, m) = 1. Then "w = 0 mod n" and "w = 0 mod m" are both true
    if and only if "w = 0 mod (mn)" is true.
    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, 06:47 AM
  2. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 09:20 PM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2010, 07:56 PM
  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