Previous Up Next

2.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=ck × 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 input :

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 input :

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

output :

[-17,35]

then input :

ichinrem([1,9],tmp)

or input :

ichrem([1,9],tmp)

Output :

[-17,315]

hence x=-17 (mod 315)
Alternative :

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

Output :

-17%315

Remark
ichrem (orichinrem)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:





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


Previous Up Next