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.

Solution

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 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

(j - i) m = (qj - qi) n.

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

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.)


[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]