Reducible polynomials over Zp.

[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!

 

[Hurkyl]

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

 

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

 

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

 

[Hurkyl]

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.

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.

 

[math-chick_41]

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

 

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

 

[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?

 

[matt grime]

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

 

[Hurkyl]

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

That'd be the harder one, perhaps.

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

 

[matt grime]

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

 

[HallsofIvy]

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, x²+ ax+ b can always be written in the form y²- c which is reducible if and only is c is a "perfect square". What percentage of numbers in Z_p 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".)

 

[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 don't know

 

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

 

[BerkMath]

- (Although if I'm right about this, I'm puzzled by BerkMath's "your formula is not quite correct".)

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