 Generalized Chinese Remainder Algorithm - Maple Help

Home : Support : Online Help : Mathematics : Number Theory : Generalized Chinese Remainder Algorithm

NumberTheory

 ChineseRemainder
 generalized Chinese remainder algorithm Calling Sequence ChineseRemainder(r, m) Parameters

 r - list of residues m - list of positive integer moduli Description

 • The "Chinese Remainder Theorem" asserts that, for pairwise relatively prime positive integers m, m, ..., m[k], and integers r, r, ..., r[k], the system of simultaneous congruences a = r (mod m), a = r (mod m), ..., a = r[k] (mod m[k]) has a solution a and a is unique modulo the product mm ... 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. Examples

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$
 > $\mathrm{ChineseRemainder}\left(\left[11,5\right],\left[31,17\right]\right)$
 ${73}$ (1)
 > $\left[73\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}31,73\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}17\right]$
 $\left[{11}{,}{5}\right]$ (2)

Note that the moduli need not be coprime.

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

The following example originates from the priest Yih-hing, 717 C.E. (See Dickson, p. 58.)

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

However, for non-coprime moduli, an answer may not exist.

 > $\mathrm{ChineseRemainder}\left(\left[2,7\right],\left[4,6\right]\right)$
 ${\mathrm{FAIL}}$ (5)
 > $\mathrm{ChineseRemainder}\left(\left[3,7,6,1\right],\left[4,12,11,6\right]\right)$
 ${127}$ (6) References

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

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