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


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
  • |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    71471721