Sunday, February 03, 2008

Little congruence result

With non-zero coprime integers n1 and n2, if f1 = r1 mod n1 and f1 = r2 mod n2, you can find f1 mod n1n2 with

f1 = r1 + jn1 mod n1n2

where j = (r2 - r1)n1-1 mod n2.

I like this result better than the Chinese Remainder theorem, as you can just go by two's and I re-discovered it.

Looks to be equivalent to what the Wikipedia calls the "method of successive substitution".

James Harris