# Implementation of the Polynomial Chinese Remainder Theorem

I would like an implementation of the Chinese Remainder Theorem for polynomials in $\mathbb{Z}[x]$, that is, a function

PolynomialCRT[{f_1,...,f_n},{m_1,...,m_n},x]


thet returns the polynomial $f\in\mathbb{Z}[x]$ of smallest degree such that $$f(x)\equiv f_i(x)\mod m_i(x),$$ where $f_i,m_i\in\mathbb{Z}[x]$ and the $m_i$ are pairwise coprime.

Any ideas?

• It should be straightforward to do this two at a time, using PolynomialExtendedGCD as the primary tool. Commented Sep 18, 2013 at 17:04
• @DanielLichtblau Thank you for your hint. Following it I succeeded in defining the function PolynomialCRT. Commented Sep 19, 2013 at 16:25
• You can post it here as a separate response. That way the Q has an A, and it is available should others in future make similar queries. That is to say, in a circumstance like this, it is not frowned upon if one answers one's own question. Commented Sep 19, 2013 at 18:53

Following Daniel's comment, I post my solution:

PolynomialCRT[pol_List, mod_List, x_] := Module[{m, q, l},
l = Length[pol];
m = Table[Times @@ Drop[mod, {i}], {i, l}];
q = Table[PolynomialExtendedGCD[m[[i]], mod[[i]], x][[2, 1]], {i, l}];
Simplify[(q pol).m]
]


There is no error checking code (for instance, pol and mod have the same length).

• Nice and short (and an upvote of course). One comment: if total degree is high, it could be faster to do it in pairs, then combining paired results in pairs, etc. That would tend to keep the degrees of the two moduli products balanced. We did this once upon a time in integer CRA code and it made a notable difference in terms of speed. Commented Sep 20, 2013 at 14:38
• +1. Sometimes the resulting polynomial is of degree more than necessary, so the last line should be changed to PolynomialRemainder[Simplify[(q pol).m], PolynomialLCM @@ mod, x]. Will Table[Times@@... line slower than procedural approach? Commented Sep 7, 2016 at 10:26