# 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| |Store|

Copyright © 1996-2017 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 _{i} and q_{j} such that

im + a = q_{i} n + r and

jm + a = q_{j} n + r.

Subtracting the first equation from the second, we get

(j - i) m = (q_{j} - q_{i}) 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| |Store|

Copyright © 1996-2017 Alexander Bogomolny61151437 |