1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Reducible polynomials over Zp.

  1. Dec 2, 2005 #1
    find a formula that depends on p
    that determines the number of reducible monic degree 2 polynomials over Zp.

    so the polynomials look like x^2+ax+b with a,b in Zp.

    I examined the case for Z3 and Z5 to try and see what was going on.
    in Z3 we had 9 monic degree 2 polynomials, 6 of them were reducible
    and 3 were not. in Z5 we had 25 monic degree 2's 15 were reducible and
    10 were not. it appears that (p(p+1))/2 is the formula but just showing two cases is obviously not enough work.
    Is my guess right and how on earth would I prove it.

    thanks!
     
    Last edited: Dec 3, 2005
  2. jcsd
  3. Dec 2, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, if you can't figure out how many are irreducible, maybe you can get it indirectly by figuring out how many are reducible?
     
  4. Dec 2, 2005 #3
    I need to figure out how many are reducible. I only know how to find out how many are irreducible and reducible by plugging and chugging and that is not good enough for proof.
     
  5. Dec 3, 2005 #4
    Your formula is not quite correct. The best way to solve this is to find the number of reducible polynomials of the form x^2+ax+b, where a,b are in Z_p, then the number of reducible quadratics, and subtract this from the total number of quadratics.
     
  6. Dec 3, 2005 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Then that's what we need to work on.

    What does it mean for a quadratic polynomial to be reducible? I know of at least two good ways of answering this question, one of which leads to a very easy counting problem, and the other leads to a fairly easy counting problem if you know a little number theory.
     
  7. Dec 3, 2005 #6
    it can be factored into two one degree polynomials
    (x-a)(x-b)
     
  8. Dec 3, 2005 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    That'd be the harder one, perhaps.

    Do you for instance know of a simple transformation of variables that in a degree n polynomial allows you to assume that the coefficient of x^{n-1} is zero? You might not in general, but you certainly know how to do it for degree 2 things, so think back to when you had to try and find roots of quadratics over C and didn't use the quadratic forumla b^2-4ac (or also think how you proved that the quadratic formula is true).
     
  9. Dec 3, 2005 #8
    to prove the quadratic formula I would just complete the square.
    should I be looking at the quadratic formula, the b^2-4ac term?
     
  10. Dec 3, 2005 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    ah, the magic words: complete the square... we after all know exactly when we can square root a number....
     
  11. Dec 4, 2005 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Actually, I thought otherwise! Counting things of the form (x-a)(x-b) seemed the easiest!
     
  12. Dec 4, 2005 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Guess I just like legendre symbols which are positive half of the time exactly (ignore the 0 case)
     
  13. Dec 4, 2005 #12

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You guys are probably confusing the poor girl now- I know you are confusing me!

    math-chick-41, What matt grime meant (I think!) when he asked "Do you for instance know of a simple transformation of variables that in a degree n polynomial allows you to assume that the coefficient of x^{n-1} is zero? " is that we can always substitute, say, [itex]x= y- \alpha[/itex] and then choose [itex]\alpha[/itex] so that the coefficient of x is 0. That is, x2+ ax+ b can always be written in the form y2- c which is reducible if and only is c is a "perfect square". What percentage of numbers in Zp are squares (including 0 and 1)? (Although if I'm right about this, I'm puzzled by BerkMath's "your formula is not quite correct".)
     
  14. Dec 4, 2005 #13
    here is what I have, x^2+ax+b over Zp is reducible if we can factor it into
    (x-s)(x-t) where s,t are in Zp. if s=t then there are p choices for s,t so there are p reducible polynomial. if s is not t then there are p choices for s and p-1 for t and when you switch s and t you get the same polynomial.

    after that I dont know
     
  15. Dec 4, 2005 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    if you count correctly, then you have counted the number of reducibles, and you know the total number of polys, hence you can work out the number of irreds. of course that is implicitly assuming factorization behaves properly in Z_p, which it does, fortunately.

    That is probably the best way to count the irreds. Mine complete the sqaure method is the way to actually tell if a given quadratic is reducibly.
     
    Last edited: Dec 4, 2005
  16. Dec 4, 2005 #15
    Carrying out the method I described earlier, you get (p(p-1)^2)/2.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Reducible polynomials over Zp.
Loading...