Chinese Remainder Theorem and Pigenhole
Let m and n be relatively prime positive integers. Then the system:
x = a (mod m)
x = b (mod n)
has a solution.
|Contact| |Front page| |Contents| |Up|
Copyright © 1996-2018 Alexander BogomolnyLet 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 = qi n + r and
jm + a = qj n + r.
Subtracting the first equation from the second, we get
(j - i) m = (qj - qi) n.
Since gcd(m, n) = 1, we conclude that n|(j - i). Note that
x = pm + a = qn + b
and x is a solution to the given system.
(The result shown is a particular and a partial case of the Chinese Remainder Theorem.)
|Contact| |Front page| |Contents| |Up|
Copyright © 1996-2018 Alexander Bogomolny71492023