Previous Up Next

6.5.21  Chinese remainders: ichinrem ichrem chrem

The Chinese Remainder Theorem states that if p1, p2, …, pn are relatively prime, then for any integers a1, a2, …an there is a number c such that c = a1 (mod p1 ), c=a2 (mod p2 ), …, c = an (mod pn ). The ichinrem command will find this value of c.
ichrem is a synonym for ichinrem.

Note that any multiple of L = lcm(p1,p2,…,pn) can be added to c and the equalities will still be true. If the pk are relatively prime, then by the Chinese remainder theorem a solution c will exist; what’s more, any two solutions will be congruent modulo the product of the pks.
If all of the arguments are given as modular integers, then the result will also be given as a modular integer c % l.

The chrem command does the same thing as ichinrem, but the input is given in a different form.

Be careful with the order of the parameters, indeed:
chrem([a,b],[p,q])=ichrem([a,p],[b,q])=ichinrem([a,p],[b,q])


Examples.


Remark.
These three commands, ichinrem, ichrem and chrem, may also be used to find the coefficients of a polynomial whose equivalence classes are known modulo several integers by using polynomials with integer coefficients instead of integers for the ak.
For example, to find ax+b modulo 315=5 × 7 × 9 under the assumptions

     
     a= 3 (mod 5 )         
a= 4 (mod 7 )          
a= 1 (mod 9 )          

and

     
     b= 1 (mod 5 )         
b= 2 (mod 7 )         
b= 3 (mod 9 )          


Example.
Input:

ichinrem((3x+1)%5,(4x+2)%7,(x+3)%9)

Output:



−17
%315
x+156%315

hence a=-17 (mod 315) and b=156 (mod 315).
As before, chrem takes the same input in a different format.
Input:

chrem([3x+1,4x+2,x+3],[5,7,9])

Output:


298 x+156,315

(note that 298 = −17 (mod 3 )15).


Previous Up Next