on http://www.cut-the-knot.com/blue/chinese.htmlit states:
When m1 and m2 are coprime their gcd is 1. By convention, a = b (mod 1) is simply understood as the usual equality a = b.
What strikes me as odd is the phrase "is simply understood
as the usual equality a = b"...
if I understand correctly 'a' and 'b' may not be equal!
i.e. 3 = 5 (mod 1) does not mean that 3 = 5.
Am I understanding 'mod' correctly?.
Consider:
n = 3 (mod 27)
n = 5 (mod 25)
Chinese remainder Theorem states this has a solution iff
3 = 5 (mod 1), since gcd(25,27)=1
a = b (mod 1) should aways be true yes? (since a (mod1) = 0
and b (mod 1) = 0) ?
In this case it would seem Chinese Remainder Theorem is
really only useful if gcd(m1,m2) > 1 otherwise it doesn't
really help you find n1 or n2, (or n).
(The solution for the above is n=30)
Steve
LAST EDITED ON Mar-31-01 AT 01:18 AM (EST)Steve, many thanks for your note. That statement is just plain wrong.
The congruence a = b (mod m) is equivalent to existence of integer t such that a = b + tm. If m = 1, this is true for any a and b (t being just the difference a - b.)
My apologies. Probably wrote that stupid remark much past midnight.
What is true is that a = b (mod 0) is equivalent to the customary a = b. But this is quite irrelevant in the context of the CRT.
Thank you again,
Alexander Bogomolny