NumberTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Number Theory : NumberTheory/ChineseRemainder

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

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.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}31,73\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{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)

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

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

Compatibility

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