Editing Chinese remainder theorem (section)

===Lagrange interpolation===
A special case of Chinese remainder theorem for polynomials is [[Lagrange interpolation]]. For this, consider {{mvar|k}} [[monic polynomial]]s of degree one:

:<math>P_i(X)=X-x_i.</math>

They are pairwise coprime if the <math>x_i</math> are all different. The remainder of the division by <math>P_i(X)</math> of a polynomial <math>P(X)</math> is <math>P(x_i)</math>, by the [[polynomial remainder theorem]].

Now, let <math>A_1, \ldots, A_k</math> be constants (polynomials of degree 0) in <math>K.</math> Both Lagrange interpolation and Chinese remainder theorem assert the existence of a unique polynomial <math>P(X),</math> of degree less than <math>k</math> such that

:<math>P(x_i)=A_i,</math>

for every <math>i.</math>

Lagrange interpolation formula is exactly the result, in this case, of the above construction of the solution. More precisely, let

:<math>\begin{align}
  Q(X)  &= \prod_{i=1}^{k}(X-x_i) \\[6pt]
 Q_i(X) &= \frac{Q(X)}{X-x_i}.
\end{align}</math>

The [[partial fraction decomposition]] of <math>\frac{1}{Q(X)}</math> is

:<math>\frac{1}{Q(X)} = \sum_{i=1}^k \frac{1}{Q_i(x_i)(X-x_i)}.</math>

In fact, reducing the right-hand side to a common denominator one gets

:<math> \sum_{i=1}^k \frac{1}{Q_i(x_i)(X-x_i)}= \frac{1}{Q(X)} \sum_{i=1}^k \frac{Q_i(X)}{Q_i(x_i)},</math>

and the numerator is equal to one, as being a polynomial of degree less than <math>k,</math> which takes the value one for <math>k</math> different values of <math>X.</math>

Using the above general formula, we get the Lagrange interpolation formula:

:<math>P(X)=\sum_{i=1}^k A_i\frac{Q_i(X)}{Q_i(x_i)}.</math>