### 5.6.22  Chinese remainders : ichinrem, ichrem

ichinrem([a,p],[b,q]) or ichrem([a,p],[b,q]) returns a list [c,lcm(p,q)] of 2 integers.
The first number c is such that

 ∀ k ∈ ℤ,    d=c+ k × lcm(p,q)

has the properties

 d=a (mod p ),    d=b (mod q )

If p and q are coprime, a solution d always exists and all the solutions are congruent modulo p*q.
Examples :
Solve :

 x = 3 (mod 5) x = 9 (mod 13)

Input :

ichinrem([3,5],[9,13])

or :

ichrem([3,5],[9,13])

Output :

[-17,65]

so x=-17 (mod 65)
We can also input :

ichrem(3%5,9%13)

Output :

-17%65

Solve :

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

First input :

tmp:=ichinrem([3,5],[4,7])

or :

tmp:=ichrem([3,5],[4,7])

Output :

[-17,35]

Then input :

ichinrem([1,9],tmp)

or :

ichrem([1,9],tmp)

Output :

[-17,315]

hence x=-17 (mod 315)
Alternative input:

ichinrem([3%5,4%7,1%9])

Output :

-17%315

Remark
ichrem (orichinrem)may be used to find the coefficients of a polynomial whose equivalence classes are known modulo several integers, for example find ax+b modulo 315=5 × 7 × 9 under the assumptions:

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

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

Input :

ichrem((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).