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

Last edited:
Related Calculus and Beyond Homework Help News on Phys.org

#### Hurkyl

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

#### 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

Staff Emeritus
Gold Member
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

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

#### 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

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

#### Hurkyl

Staff Emeritus
Gold Member
math-chick_41 said:
it can be factored into two one degree polynomials
(x-a)(x-b)
mattgrime said:
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

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

#### HallsofIvy

Homework Helper
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".)

#### 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

#### matt grime

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:

#### BerkMath

HallsofIvy said:
- (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.

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving