next up previous contents index
suivant: Solving a2 + b2 monter: Integers (and Gaussian Integers) précédent: Chinese remainders : ichinrem,   Table des matières   Index


Chinese remainders for lists of integers : chrem

chrem takes as argument 2 lists of integers of the same size.
chrem returns a list of 2 integers.
For example, chrem([a,b,c],[p,q,r]) returns the list [x,lcm(p,q,r)] where x=a mod p and x=b mod q and x=c mod r.
A solution x always exists if p, q, r are mutually primes, and all the solutions are equal modulo p*q*r.
BE CAREFULL with the order of the parameters, indeed :
chrem([a,b],[p,q])=ichrem([a,p],[b,q])=
ichinrem([a,p],[b,q])

Examples :
Solve :

$\displaystyle \tt\left \{ \begin{array}{rl} x=&3\ (\bmod\ 5)\\
x=&9\ (\bmod\ 13) \end{array}\right.$

Input :
chrem([3,9],[5,13])
Output :
[-17,65]
so, x=-17 (mod 65)
Solve :

$\displaystyle \tt\left \{ \begin{array}{rl} x=&3\ (\bmod\ 5)\\
x=&4\ (\bmod\ 6) \\
x=&1\ (\bmod\ 9)\end{array}\right.$

Input :
chrem([3,4,1],[5,6,9])
Output :
[28,90]
so x=28 (mod 90)
Remark
chrem may be used to find coefficients of polynomial which class are known modulo several integers, for example find ax + b modulo 315 = 5×7×9 under the assumptions:

$\displaystyle \tt\left \{ \begin{array}{rl} a=&3\ (\bmod\ 5)\\
a=&4\ (\bmod\ 7) \\
a=&1\ (\bmod\ 9) \end{array}\right.$,    $\displaystyle \tt\left \{ \begin{array}{rl} b=&1\ (\bmod\ 5)\\
b=&2\ (\bmod\ 7) \\
b=&3\ (\bmod\ 9) \end{array}\right.$

Input :
chrem([3x+1,4x+2,x+3],[5,7,9])
Output :
[-17x+156),315]
hence, a=-17 (mod 315) et que b=156 (mod 315).


next up previous contents index
suivant: Solving a2 + b2 monter: Integers (and Gaussian Integers) précédent: Chinese remainders : ichinrem,   Table des matières   Index
giac documentation written by Renée De Graeve and Bernard Parisse