Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The Chinese Remainder Theorem for moduli that aren't relatively prime

  1. Nov 22, 2009 #1
    I am looking into proving that the Chinese Remainder Theorem will work for two pairs of congruences IFF a congruent to b modulo(gcd(n,m)) for

    x congruent to a mod(n) and x congruent to b mod(m).

    I have gotten one direction, that given a solution to the congruences mod(m*n), then a congruent to b mod(gcd(m,n)).

    My issue is going the other way, given a congruent to b mod(gcd(m,n)), show a solution to the congruences exists mod(m*n).

    Can anybody help me with a start? I tried expressing the relationship between a and b and using that to determine what x would have to be, but I'm not convinced of the results.
  2. jcsd
  3. Nov 22, 2009 #2
    OK, I got that the gcd(n,m)|(a-b)-> x==a mod(n) and x==b mod(m) will have a solution, but showing that that solution is restricted to the modulus of m*n is giving me troubles...
  4. Dec 1, 2009 #3
    AFAIK, the solution (if it exists) is unique modulo lcm(m,n), not modulo m*n.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook