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

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

Related material Read more...


	17 rooks on a Chessboard
	Pigeonhole in a Chessboard
	Pigeonhole in Concurrent Cuts
	Monochromatic Rectangle in a 2-coloring of the Plane
	Polynomial and Integer Division
	Power of three that ends with 001
	Pigeonhole Principle (subsets)
	Pigeonhole in Integer Differences
	Four Numbers, Six Differences, GCD of the Products

40614825

Chinese Remainder Theorem and Pigenhole

Related materialRead more...

Related material
Read more...