# Reducible polynomials over Zp.

1. Dec 2, 2005

### math-chick_41

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. Dec 2, 2005

### Hurkyl

Staff Emeritus
Well, if you can't figure out how many are irreducible, maybe you can get it indirectly by figuring out how many are reducible?

3. Dec 2, 2005

### math-chick_41

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.

4. Dec 3, 2005

### BerkMath

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.

5. Dec 3, 2005

### Hurkyl

Staff Emeritus
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.

6. Dec 3, 2005

### math-chick_41

it can be factored into two one degree polynomials
(x-a)(x-b)

7. Dec 3, 2005

### matt grime

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).

8. Dec 3, 2005

### math-chick_41

to prove the quadratic formula I would just complete the square.
should I be looking at the quadratic formula, the b^2-4ac term?

9. Dec 3, 2005

### matt grime

ah, the magic words: complete the square... we after all know exactly when we can square root a number....

10. Dec 4, 2005

### Hurkyl

Staff Emeritus
Actually, I thought otherwise! Counting things of the form (x-a)(x-b) seemed the easiest!

11. Dec 4, 2005

### matt grime

Guess I just like legendre symbols which are positive half of the time exactly (ignore the 0 case)

12. Dec 4, 2005

### HallsofIvy

Staff Emeritus
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, $x= y- \alpha$ and then choose $\alpha$ 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".)

13. Dec 4, 2005

### math-chick_41

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

14. Dec 4, 2005

### matt grime

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
15. Dec 4, 2005

### BerkMath

Carrying out the method I described earlier, you get (p(p-1)^2)/2.