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!

Counting Number of Irreducibles

  1. Jul 13, 2008 #1
    The problem statement, all variables and given/known data
    Let p be a prime.
    (a) Determine the number of irreducible polynomials over Zp of the form x2 + ax + b.
    (b) Determine the number of irreducible quadratic polynomials over Zp.

    The attempt at a solution
    A nonzero, nonunit polynomial f(x) in Zp[x] is irreducible if it equals the product of two polynomials in Zp[x], one of them being a unit of Zp[x]. But does Zp[x] have any units? I find it hard to imagine that there are polynomials g(x) and h(x) in Zp[x] with g(x)h(x) = 1, unless of course g(x) = h(x) = ±1.
     
  2. jcsd
  3. Jul 13, 2008 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    just considering the leading terms of g and h will show you this is a trivial statement.

    You could also try counting the reducible quadratics, since that is also easy.
     
  4. Jul 13, 2008 #3
    I think I understand: Let axm and bxn be the leading terms of g(x) and h(x). If g(x)h(x) = 1, then abxm+n must equal 0 so ab must equal p but this is impossible. It follows that Zp[x] has no units so the answer both (a) and (b) is 0?
     
  5. Jul 13, 2008 #4
    Oh, and how does counting the reducible quadratics help in counting the irreducible ones?
     
  6. Jul 13, 2008 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    How long did you think about that (the counting irreducibles)?
     
    Last edited: Jul 13, 2008
  7. Jul 13, 2008 #6
    Not long. However, something just occurred to me: There are p3 polynomials in Zp[x] so the number of irreducibles is just p3 minus the number of reducibles. Is that right?
     
  8. Jul 13, 2008 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    There are *not* p^3 polys in Z_p[x] - there may be p^3 in some subset of that. But it is certainly true that a poly is either reducible or irreducible, and not both, so if you know how many in total there are, and how many of one type, then you know how many of the other there are.

    And there are not p^3 quadratics, if that was what you meant, since the leading coefficient has to be non-zero.
     
  9. Jul 13, 2008 #8
    Yes, I did mean p3 quadratics. Sorry about that. So would (p - 1)p2 be a better estimate?

    I'm confused though: If Zp[x] doesn't have any units (cf. my second post), how can there be irreducible polynomials?
     
  10. Jul 13, 2008 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    In what way does x not satisfy the definition of irreducible? How are you going to write that as a product of two other polynomials of strictly smaller degree. And why are there no units? You even wrote out 2 units in your first post.
     
  11. Jul 13, 2008 #10
    x is irreducible since the only way to write it as a product g(x)h(x) is by setting g(x) = 1 and h(x) = x or vice-versa and 1 is a unit. I understand that.

    When I wrote "Zp[x] doesn't have any units", I meant nonconstant units. I can't think of an example unit in Zp[x] that is nonconstant. This is probably why I wrote that there aren't any.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?