10.9 ChineseRem

ChineseRem( moduli, residues )

ChineseRem returns the combination of the residues modulo the moduli, i.e., the unique integer c from [0..Lcm(moduli)-1] such that c = residues[i] modulo moduli[i] for all i, if it exists. If no such combination exists ChineseRem signals an error.

Such a combination does exist if and only if
residues[i]=residues[k] mod Gcd(moduli[i],moduli[k]) for every pair i, k. Note that this implies that such a combination exists if the moduli are pairwise relatively prime. This is called the Chinese remainder theorem.

    gap> ChineseRem( [ 2, 3, 5, 7 ], [ 1, 2, 3, 4 ] );
    53
    gap> ChineseRem( [ 6, 10, 14 ], [ 1, 3, 5 ] );
    103
    gap> ChineseRem( [ 6, 10, 14 ], [ 1, 2, 3 ] );
    Error, the residues must be equal modulo 2 

Previous Up Top Next
Index