Chinese remainders

11.2.10 Chinese remainders

Theorem 4 (Chinese remainders) I R(x) and Q(x) are relatively prime polynomials, then for any polynomials A(x) and B(x), there exists a polynomial P(x) such that:

P(x)	≡ A(x) (mod R(x) )
P(x)	≡ B(x) (mod Q(x) )

The chinrem command finds the polynomial P.

chinrem takes two mandatory arguments and one optional argument:
- [A,R] and [B,Q], two lists, each consisting of two polynomials given by expressions or lists of coefficients in decreasing order.
- Optionally, if the polynomials are expressions, x, the main variable (by default x).
chinrem([A,R],[B,Q] ⟨,x⟩) returns the list [P,S], where P and S are polynomials such that:

S =R Q

P ≡ A(mod R )

P ≡ B(mod Q )

If R and Q are coprime, a solution P always exists and all the solutions are congruent modulo S=R Q.

Examples

Find P such that

⎧
⎨
⎩

P(x)≡ x	(mod x²+1 ),
P(x)≡ x−1	(mod x²−1 ).

chinrem([[1,0],[1,0,1]],[[1,-1],[1,0,-1]])

⎡
⎢
⎢
⎣

−

,1,−

⎤
⎥
⎥
⎦

⎡
⎣

1,0,0,0,−1

⎤
⎦

⎤
⎥
⎥
⎦

or:

chinrem([x,x^2+1],[x-1,x^2-1])

⎡
⎢
⎢
⎣

−

x²

+x−

,x⁴−1

⎤
⎥
⎥
⎦

hence P(x)≡ −x²−2x+1/2 (mod x⁴−1 ).

chinrem([[1,2],[1,0,1]],[[1,1],[1,1,1]])

⎡
⎣

−1,−1,0,1

⎤
⎦

⎡
⎣

1,1,2,1,1

⎤
⎦

or:

chinrem([y+2,y^2+1],[y+1,y^2+y+1],y)

⎡
⎣

−y³−y²+1,y⁴+y³+2 y²+y+1

⎤
⎦