Results 1 to 6 of 6

Math Help - Independence with mod

  1. #1
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8

    Independence with mod

    How would I go about proving that \sum_{i=1}^{p-1}a_ix^i \equiv 0 \ (mod \ p) \Rightarrow a_i \equiv 0 \ (mod \ p) for all a_i.

    The way I'm doing it now assumes that there is one coefficient which is not congruent to 0 mod p. This implies that the variable must be congruent to 0 mod p, but since the summation is true for all x, we get our contradiction.

    My problem is that I'm assuming that there is only one coefficient which isn't congruent to 0 mod p. In the case of 2 coefficients not congruent to 0, I think I can do it by showing that the two terms have to be additive inverses, and eventually we get back to x being forced to zero (contradiction). What do I do in the case of more than 2 coefficients not being congruent to 0 mod p?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Prove that if a_n \not\equiv 0 (\bmod.p) then p(x)=a_n\cdot x^n +...+a_1\cdot x + a_0 can have at most n roots module p - try induction-. (*)

    Now in your case, suppose a_i \not\equiv 0 (\bmod.p) for some 0<i<p then by (*) it can have at most k roots module p for some k<p -the greatest nonzero coefficient mod. p-, but it has p roots! Contradiction
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Um ... wouldn't my case have p-1 roots? Since the highest power is p-1. So the contradiction wouldn't quite work ....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Bingk View Post
    Um ... wouldn't my case have p-1 roots? Since the highest power is p-1. So the contradiction wouldn't quite work ....
    How many remainders are there module p? Each of them is a root of your polynomial - mod. p-
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Can you use algebra?
    It is a theorem that if F is a field, the polynomial ring F[x] is a unique factorization domain. Since \mathbb{Z}/p\mathbb{Z} = \mathbb{F}_p is a field, \mathbb{F}_p[x] is a unique factorization domain, which implies that a polynomial having degree n can have at most n roots in \mathbb{F}_p. In particular, a nonzero polynomial of degree  \leq p-1 can have at most p-1 roots. In other words, if it has p roots it must be the zero polynomial.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    AH!!! Okay ... I think it just clicked together ... sorry, alot of the stuff you guys are saying is kinda advanced for me, hehehe. Um, I didn't study number theory with an algebra approach, so I'm not too familiar with all that notation about fields, rings, and such ... but I did look it up .

    I think the two of you are kinda doing the same thing ... and this is what I basically get.

    The polynomial I gave has p roots (since it works for all 0<=x<p). But, the polynomial is of order p-1, so it should have at most p-1 roots. Which is the contradiction that PaulRS was talking about, so all the coefficients should be congruent to 0 mod p. As for Bruno, I'm not sure how/why we can say that (aside from PaulRS way ) it must be the zero polynomial. This is probably because I don't know enough about fields and such .

    Thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 15th 2010, 01:24 PM
  2. Independence
    Posted in the Statistics Forum
    Replies: 0
    Last Post: October 26th 2010, 04:20 PM
  3. Independence
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: February 6th 2010, 07:41 PM
  4. independence
    Posted in the Advanced Statistics Forum
    Replies: 8
    Last Post: January 27th 2010, 10:29 PM
  5. independence
    Posted in the Advanced Statistics Forum
    Replies: 7
    Last Post: September 5th 2009, 10:53 PM

Search Tags


/mathhelpforum @mathhelpforum