NumberTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

NumberTheory

  

ChineseRemainder

  

generalized Chinese remainder algorithm

 

Calling Sequence

Parameters

Description

Examples

Compatibility

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

withNumberTheory:

ChineseRemainder11,5,31,17

73

(1)

73mod31,73mod17

11,5

(2)

Note that the moduli need not be coprime.

ChineseRemainder3,7,4,6

7

(3)

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

ChineseRemainder2,7,4,6

FAIL

(4)

ChineseRemainder3,7,6,1,4,12,11,6

127

(5)

Compatibility

• 

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

• 

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

See Also

chrem

igcd

mod

NumberTheory

NumberTheory[AreCoprime]