Results 1 to 2 of 2

Thread: chinese remainder theorem to show a unique polynomial

  1. #1
    Senior Member
    Joined
    Feb 2008
    Posts
    410

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Dec 28th 2011, 08:53 AM
  2. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Jun 21st 2011, 06:47 AM
  3. Chinese remainder theorem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Nov 20th 2009, 12:57 PM
  4. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 1st 2008, 01:27 AM
  5. Chinese Remainder Theorem 3
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 27th 2007, 11:27 AM

/mathhelpforum @mathhelpforum