Online Help

The "Chinese Remainder Theorem" asserts that, for pairwise relatively prime positive integers m[1], m[2], ..., m[k], and integers r[1], r[2], ..., r[k], the system of simultaneous congruences a = r[1] (mod m[1]), a = r[2] (mod m[2]), ..., a = r[k] (mod m[k]) has a solution a and a is unique modulo the product m[1]m[2] ... m[k] of the m[i].

More generally, this system of simultaneous congruences has a solution if, and only if, each pair of distinct moduli are congruent modulo their greatest common divisor. In this case, the solution is uniquely determined modulo the least common multiple of the moduli.

The ChineseRemainder( r, m ) command computes, if possible, an integer a such that a mod m[ i ] = r[ i ], for all i.

Unlike the chrem command, which requires the moduli to be pairwise coprime, the ChineseRemainder function solves the generalized problem with moduli that need not be pairwise coprime.

In the event that a solution to the simultaneous congruences does not exist, the ChineseRemainder function returns the value FAIL.

$\mathrm{with}\left(\mathrm{NumberTheory}\right)\:$

$\mathrm{ChineseRemainder}\left(\left[11\,5\right]\,\left[31\,17\right]\right)$

$73$

$\left[73\mathbf{mod}31\,73\mathbf{mod}17\right]$

$\left[11\,5\right]$

$\mathrm{ChineseRemainder}\left(\left[3\,7\right]\,\left[4\,6\right]\right)$

$7$

$\mathrm{ChineseRemainder}\left(\left[1\,2\,5\,5\right]\,\left[2\,3\,6\,12\right]\right)$

$5$

$\mathrm{ChineseRemainder}\left(\left[2\,7\right]\,\left[4\,6\right]\right)$

$\mathrm{FAIL}$

$\mathrm{ChineseRemainder}\left(\left[3\,7\,6\,1\right]\,\left[4\,12\,11\,6\right]\right)$

$127$

L. E. Dickson, History of the theory of numbers: Volume II, Diophantine Analysis , Dover, 2005 (Reprint of the 1919 edition by the Carnegie Institute.)

The NumberTheory[ChineseRemainder] command was introduced in Maple 2017.

For more information on Maple 2017 changes, see Updates in Maple 2017 .