# Thread: chinese remainder theorem to show a unique polynomial

1. ## chinese remainder theorem to show a unique polynomial

The problem statement:

Let $\displaystyle n_0,\cdots,n_m\in\mathbb{Z}$. Prove that there is a unique $\displaystyle f(x)\in\mathbb{Q}[x]$ of degree $\displaystyle \leq m$ such that $\displaystyle f(i)=n_i$ for all $\displaystyle i=0,\cdots,m$. [Hint: Use the Chinese remainder theorem.]
Notice that $\displaystyle n_0,\cdots,n_m$ need NOT be pairwise coprime.

It seems to me that this problem is equivalent to showing that the linear system $\displaystyle Ax=b$, where

$\displaystyle A=\left(\begin{array}{ccc}0^0&\cdots&0^m\\\vdots&\ vdots&\vdots\\m^0&\cdots&m^m\end{array}\right)$, $\displaystyle x=\left(\begin{array}{c}a_0\\\vdots\\a_m\end{array }\right)$ and $\displaystyle b=\left(\begin{array}{c}n_0\\\vdots\\n_m\end{array }\right)$,

has exactly one solution, which in turn is equivalent to showing that $\displaystyle A$ is invertible.

However, the hint tells me to use the Chinese remainder theorem---and I don't see how that's relevant.

Any help would be much appreciated. Thanks!

2. Another way to look at this problem is to set up a system of linear congruences. We can look at a concrete example first - you should be able to generalize it from there.

Suppose we want to find a polynomial $\displaystyle f$ such that $\displaystyle f(1)=2, f(2)=5, f(3)=13$. If we treat $\displaystyle f(x)$ as an unknown, we have a system of linear (polynomial) congruences:

$\displaystyle f(x)=2\pmod{x-1}$
$\displaystyle f(x)=5\pmod{x-2}$
$\displaystyle f(x)=13\pmod{x-3}$

If you run the Chinese Remainder Theorem algorithm on this, you find that the polynomial is $\displaystyle f(x)=4-\frac{9 x}{2}+\frac{5 x^2}{2}$. It is automatically guaranteed to be unique by the statement of the theorem.