chinese remainder theorem to show a unique polynomial

**hatsoff** · January 28th 2011, 11:30 AM

The problem statement:

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!

**roninpro** · January 28th 2011, 04:54 PM

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.

Thread: chinese remainder theorem to show a unique polynomial

LinkBack

Thread Tools

Display

chinese remainder theorem to show a unique polynomial

Similar Math Help Forum Discussions

Chinese Remainder Theorem.

Chinese remainder theorem

Chinese remainder theorem

Chinese Remainder Theorem

Chinese Remainder Theorem 3