Chinese Remainder Theorem

According to D. Wells, the following problem was posed by Sun Tsu Suan-Ching (4th century AD):

There are certain things whose number is unknown. Repeatedly divided by $3,$ the remainder is $2;$ by $5$ the remainder is $3;$ and by $7$ the remainder is $2.$ What will be the number?

Oystein Ore mentions another puzzle with a dramatic element from Brahma-Sphuta-Siddhanta (Brahma's Correct System) by Brahmagupta (born 598 AD):

An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?

Problems of this kind are all examples of what universally became known as the Chinese Remainder Theorem. In mathematical parlance the problems can be stated as finding n, given its remainders of division by several numbers $m_{1}, m_{2}, \ldots, m_{k}:$

(1)

$\begin{align} n &= n_{1}\space(\mbox{mod} m_{1})\\ n &= n_{2}\space(\mbox{mod} m_{2})\\ &\space\ldots\\ n &= n_{k}\space(\mbox{mod} m_{k}) \end{align}$

The modern day theorem is best stated with a couple of useful notations. For non-negative integers $m_{1}, m_{2}, \ldots, m_{k},$ their greatest common divisor is defined as

$\mbox{gcd}(m_{1}, m_{2}, \ldots, m_{k}) = \mbox{max}\{s: s|m_{i}, \space\mbox{for}\space i = 1, \ldots, k\},$

where, as always, $s|m$ means that $s$ divides $m$ exactly. The least common multiple of $k$ numbers is defined as

$\mbox{lcm}(m_{1}, m_{2}, \ldots, m_{k}) = \mbox{min}\{s: s \gt 0 \space\mbox{and}\space m_{i}|s, \space\mbox{for}\space i = 1, \ldots, k\},$

Both $\mbox{gcd}()$ and $\mbox{lcm}()$ are symmetric functions of their arguments. They are complementary in the sense that, for $k = 2,$

$\mbox{gcd}(m_{1}, m_{2})\cdot\mbox{lcm}(m_{1}, m_{2}) = m_{1}\cdot m_{2}.$

(A proof and an interactive illustration for this identity appears elsewhere.)

However, for $k \gt 2$ a similar identity does not in general hold. For an example, consider two triplets: $\{2, 4, 16\}$ and $\{2, 8, 16\}.$ Both have exactly the same $\mbox{gcd}$ and $\mbox{lcm}$ but obviously different products. On the other hand, both $\mbox{gcd}$ and $\mbox{lcm}$ are associative:

$\mbox{gcd}(m_{1},\space(\mbox{gcd}(m_{2}, m_{3})) = \mbox{gcd}(\mbox{gcd}(m_{1}, m_{2}), m_{3})$

and, both equal $\mbox{gcd}(m_{1}, m_{2}, m_{3}).$ Similarly,

$\mbox{lcm}(m_{1},\space(\mbox{lcm}(m_{2}, m_{3})) = \mbox{lcm}(\mbox{lcm}(m_{1}, m_{2}), m_{3}).$

Note

If, for a prime $p,$ $p^{\alpha _{i}}|m_{i},$ with $\alpha _{i}$ being the largest exponent with that property, then $p^{\alpha }|\mbox{lcm}(m_{1}, m_{2}, \ldots, m_{k}),$ where $\alpha = \mbox{max}\{\alpha _{i}\}$ and $\alpha$ is the largest exponent with that property. Similarly, the greatest common divisor of several numbers is the product of the largest powers of the primes that divide all the given numbers.

Associativity allows one to proceed a step at a time with an inductive argument without putting all eggs into a basket at once. Jumping at the opportunity I'll prove the most basic case of $k = 2.$

Theorem 1

Two simultaneous congruences

$\begin{align} n &= n_{1}\space(\mbox{mod}\space m_{1}) \space\mbox{and}\\ n &= n_{2}\space(\mbox{mod}\space m_{2}) \end{align}$

are only solvable when $n_{1} = n_{2}\space(\mbox{mod}\space \mbox{gcd}(m_{1}, m_{2})).$ The solution is unique modulo $\mbox{lcm}(m_{1}, m_{2}).$

(When $m_{1}$ and $m_{2}$ are coprime their $\mbox{gcd}$ is $1.$ By convention, $a = b\space(\mbox{mod}\space 1)$ holds for any $a$ and $b.)$

Proof

By a generalization of Euclid's algorithm, there are integers $s$ and $t$ such that

$tm_{1} + sm_{2} = \mbox{gcd}(m_{1}, m_{2}).$

Since $n_{2} - n_{1} = 0\space(\mbox{mod}\space\mbox{gcd}(m_{1}, m_{2})),$ for some, possibly different $t$ and $s,$

(2)

$tm_{1} + sm_{2} = n_{2} - n_{1}.$

Then $n = tm_{1} + n_{1} = -sm_{2} + n_{2}$ satisfies both congruences in the theorem. This proves the existence of a solution.

To prove the uniqueness part, assume $n$ and $N$ satisfy the two congruences. Taking the differences we see that

$N - n = 0\space(\mbox{mod}\space m_{1})$ and $N - n = 0\space(\mbox{mod} m_{2})$

which implies $N - n = 0\space(\mbox{mod}\space \mbox{lcm}(m_{1}, m_{2})).$

As was previously stated, a more general theorem can now be proved by induction.

Theorem 2

The simultaneous congruences (1)

$\begin{align} n &= n_{1} & (\mbox{mod} m_{1})\\ n &= n_{2} & (\mbox{mod} m_{2})\\ &\space\ldots\\ n &= n_{k} & (\mbox{mod} m_{k}) \end{align}$

are only solvable when $n_{i} = n_{j}\space(\mbox{mod}\space\mbox{gcd}(m_{i}, m_{j})),$ for all $i$ and $j,$ $i \ne j.$ The solution is unique modulo $\mbox{lcm}(m_{1}, m_{2}, \ldots, m_{k}).$

Proof

Theorem 1 serves the initial step verification. Assume the theorem holds for $k$ congruences and consider $k + 1$ of them.

$\begin{align} n &= n_{1} & (\mbox{mod}\space m_{1})\\ n &= n_{2} & (\mbox{mod}\space m_{2})\\ &\space\ldots &\\ n &= n_{k} & (\mbox{mod}\space m_{k})\\ n &= n_{k+1} & (\mbox{mod}\space m_{k+1}) \end{align}$

Let $s$ be a solution to the first $k$ equations. Then the congrurence $n = s\space(\mbox{mod}\space \mbox{lcm}(m_{1}, m_{2}, \ldots, m_{k}))$ has a solution. (Observe that every solution of the latter also satisfies the first $k$ congruences.) To be able to apply the already proven Theorem 1, we need to show that

(3)

$s = n_{k+1}\space(\mbox{mod}\space \mbox{gcd}(\mbox{lcm}(m_{1}, \ldots, m_{k}), m_{k+1})).$

Let's write $g_{u}= \mbox{gcd}(m_{u}, m_{k+1}), u = 1, \ldots, k.$ Then we know that $n_{u}= n_{k+1}\space(\mbox{mod}\space g_{u})$ for these values of $u.$ But $n_{u}= s + t_{u}m_{u},$ for some $t_{u},$ implying $n_{k+1} = s + t_{u}m_{u}\space(\mbox{mod}\space g_{u})$ so that

$s = n_{k+1}\space(\mbox{mod}\space g_{u}),\space u = 1, 2, \ldots, k.$

If so,

$\begin{align} s &= n_{k+1}\space(\mbox{mod}\space \mbox{lcm}(g_{1}, \ldots, g_{k}))\\ &= n_{k+1}\space(\mbox{mod}\space \mbox{lcm}(\mbox{gcd}(m_{1}, m_{k+1}), \ldots, \mbox{gcd}(m_{k}, m_{k+1})))\\ &= n_{k+1}\space(\mbox{mod}\space \mbox{gcd}(\mbox{lcm}(m_{1}, \ldots, m_{k}), m_{k+1})), \end{align}$

because $\mbox{lcm}(\mbox{gcd}(m_{1}, m_{k+1}), \ldots, \mbox{gcd}(m_{k}, m_{k+1})) = \mbox{gcd}(\mbox{lcm}(m_{1}, \ldots, m_{k}), m_{k+1}).$

Thus the system

$\begin{align} n &= s\space(\mbox{mod}\space \mbox{lcm}(m_{1}, m_{2}, \ldots, m_{k}))\\ n &= n_{k+1}\space(\mbox{mod}\space m_{k+1}) \end{align}$

has a solution which is unique modulo

$\mbox{lcm}(\mbox{lcm}(m_{1}, m_{2}, \ldots, m_{k}), m_{k+1}) = \mbox{lcm}(m_{1}, m_{2}, \ldots, m_{k}, m_{k+1}).$

It also satisfies the whole set of $k + 1$ congruences.

Corollary

The simultaneous congruences (1)

$\begin{align} n &= n_{1}\space(\mbox{mod}\space m_{1})\\ n &= n_{2}\space(\mbox{mod}\space m_{2})\\ &\space\ldots\\ n &= n_{k}\space(\mbox{mod}\space m_{k}) \end{align}$

where all $m_{i}$'s are pairwise coprime has a unique solution modulo $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{k}.$

If some $m_{i}$'s are not mutually prime, a solution may not exist unless the corresponding congruence agree. For example, the system $n = 1\space(\mbox{mod}\space 2)$ and $n = 2\space(\mbox{mod}\space 4)$ has not solution, while the system $n = 1\space(\mbox{mod}\space 2)$ and $n = \pm 1\space(\mbox{mod}\space 4)$ does.

Let's now solve the two problems we started the page with.

Problem #1

Solve

$\begin{cases} \mbox{p1}: & x = 2\space(\mbox{mod}\space 3)\\ \mbox{p2}: & x = 3\space(\mbox{mod}\space 5)\\ \mbox{p3}: & x = 2\space(\mbox{mod}\space 7) \end{cases}$

From $\mbox{p1}$, $x = 3t + 2,$ for some integer $t.$ Substituting this into $\mbox{p2}$ gives $3t = 1\space(\mbox{mod}\space 5).$ Looking up $1/3$ in the division table modulo $5,$ this reduces to a simpler equation

$\mbox{p4}:\space\space t = 2\space(\mbox{mod}\space 5)$

which, in turn, is equivalent to $t = 5s + 2$ for an integer $s.$ Substitution into $x = 3t + 2$ yields $x = 15s + 8.$ This now goes into $\mbox{p3}: 15s + 8 = 2\space(\mbox{mod}\space 7).$ Casting out 7 gives $s = 1\space(\mbox{mod}\space 7).$ From here, $s = 7u + 1$ and, finally, $x = 105 u + 23.$

Note that $105 = \mbox{lcm}(3, 5, 7).$ Thus we have solutions $23, 128, 233, \ldots$

Problem #2

Solve

$\begin{cases} \mbox{q1}: & x = 1\space(\mbox{mod}\space 2)\\ \mbox{q2}: & x = 1\space(\mbox{mod}\space 3)\\ \mbox{q3}: & x = 1\space(\mbox{mod}\space 4)\\ \mbox{q4}: & x = 1\space(\mbox{mod}\space 5)\\ \mbox{q5}: & x = 1\space(\mbox{mod}\space 6)\\ \mbox{q6}: & x = 0\space(\mbox{mod}\space 7)\\ \end{cases}$

With the experience we acquired so far, the combination of $\mbox{q1}-\mbox{q5}$ is equivalent to

$\mbox{q7}:\space\space x = 1\space(\mbox{mod}\space 60),$

$x = 60t + 1.$ Plugging this into $\mbox{q6}$ gives $60t = -1\space(\mbox{mod}\space 7).$ Casting out $7$ simplifies this to $4t = 6\space(\mbox{mod}\space 7)$ and then $2t = 3\space(\mbox{mod}\space 7).$ From the division tables modulo $7,$ $3/2 = 5\space(\mbox{mod}\space 7).$ Therefore, $t = 7u + 5.$ Finally, $x = 420u + 301.$ Allowing for an average size farmer, the most likely number of eggs she might expect to be compensated for is $301.$

Note: The Chinese Remainder Theorem finds an important application in the clendrical calculations.

References

  1. H. Davenport, The Higher Arithmetic, Cambridge University Press; 7 edition (December 9, 1999)
  2. P. J. Davis and R. Hersh, The Mathematical Experience, Houghton Mifflin Company, Boston, 1981
  3. U. Dudley, Elementary Number Theory, Dover, 2008
  4. R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
  5. Oystein Ore, Number Theory and Its History, Dover Publications, 1976
  6. D. Wells, The Penguin Book of Curious and Interesting Puzzles, Penguin Books, 1992

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 62063547

Search by google: