Results 1 to 2 of 2

Math Help - 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 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!
    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 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.
    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: December 28th 2011, 09:53 AM
  2. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 21st 2011, 07:47 AM
  3. Chinese remainder theorem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 20th 2009, 01:57 PM
  4. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2008, 02:27 AM
  5. Chinese Remainder Theorem 3
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 27th 2007, 12:27 PM

/mathhelpforum @mathhelpforum