|Nov22-09, 04:56 PM||#1|
The Chinese Remainder Theorem for moduli that aren't relatively prime
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.
|Nov22-09, 07:00 PM||#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...
|Dec1-09, 02:01 AM||#3|
AFAIK, the solution (if it exists) is unique modulo lcm(m,n), not modulo m*n.
|Similar Threads for: The Chinese Remainder Theorem for moduli that aren't relatively prime|
|Chinese Remainder Theorem!!!||Linear & Abstract Algebra||5|
|The Chinese Remainder Theorem (the CRT)||Brain Teasers||5|
|Chinese Remainder Theorem||Calculus & Beyond Homework||1|
|Chinese Remainder Theorem||Calculus & Beyond Homework||9|
|Chinese Remainder Theorem||Linear & Abstract Algebra||3|