### 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 x2+1 ),
P(x)≡x−1 | (mod x2−1 ).

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

⎡
⎢
⎢
⎣

⎡
⎢
⎢
⎣

−

1
2

,1,−

1
2

⎤
⎥
⎥
⎦

,

⎡
⎣

1,0,0,0,−1

⎤
⎦

⎤
⎥
⎥
⎦

or:

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

⎡
⎢
⎢
⎣

−

x2
2

+x−

1
2

,x4−1

⎤
⎥
⎥
⎦

hence P(x)≡ −x2−2x+1/2 (mod x4−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)

| ⎡ ⎣ | −y3−y2+1,y4+y3+2 y2+y+1 | ⎤ ⎦