Chinese Remainder Theorem
| |
Let m and n be relatively prime positive integers. Then the system:
| |
x = a (mod m)
x = b (mod n)
|
has a solution.
|
Solution
Copyright © 1996-2010 Alexander Bogomolny
| |
Let m and n be relatively prime positive integers. Then the system:
| |
x = a (mod m)
x = b (mod n)
|
has a solution.
|
We may assume that 0 ≤ a < m and 0 ≤ b < n. Let us consider the n integers
| (*) |
a, m + a, 2m + a, ..., (n - 1)m + a.
|
They all have the same remainder a when divided by m. They all have different remainders when divided by n. For, suppose otherwise, that some two of them have the same remainder r when divided by n. Let the two numbers be im + a and jm + a, where 0 ≤ i < j ≤ n - 1. Then there are integers qi and qj such that
| |
im + a = qi n + r and
jm + a = qj n + r.
|
Subtracting the first equation from the second, we get
Since gcd(m, n) = 1, we conclude that n|(j - i). Note that 0 < j - i ≤ n - 1. A contradiction. Thus
the n integers (*) have distinct remainders when divided by n. That is, each of the n numbers 0, 1, 2, ..., n - 1 occurs as a remainder. In particular, the number b does. Let p be the integer with 0 ≤ p ≤ n - 1 such that the number x = pm + a has remainder b when divided by n. Then for some integer q, x = qn + b. This exactly means that
and x is a solution to the given system.
(The result shown is a particular and a partial case of the Chinese Remainder Theorem.)
Copyright © 1996-2010 Alexander Bogomolny
|
