# chinese remainder theorem to show a unique polynomial

• Jan 28th 2011, 11:30 AM
hatsoff
chinese remainder theorem to show a unique polynomial
The problem statement:

Quote:

Let $n_0,\cdots,n_m\in\mathbb{Z}$. Prove that there is a unique $f(x)\in\mathbb{Q}[x]$ of degree $\leq m$ such that $f(i)=n_i$ for all $i=0,\cdots,m$. [Hint: Use the Chinese remainder theorem.]
Notice that $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 $Ax=b$, where

$A=\left(\begin{array}{ccc}0^0&\cdots&0^m\\\vdots&\ vdots&\vdots\\m^0&\cdots&m^m\end{array}\right)$, $x=\left(\begin{array}{c}a_0\\\vdots\\a_m\end{array }\right)$ and $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 $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!
• Jan 28th 2011, 04:54 PM
roninpro
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 $f$ such that $f(1)=2, f(2)=5, f(3)=13$. If we treat $f(x)$ as an unknown, we have a system of linear (polynomial) congruences:

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

If you run the Chinese Remainder Theorem algorithm on this, you find that the polynomial is $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.