# Reducible Polynomials

• October 10th 2010, 02:50 AM
demode
Reducible Polynomials
Let $p$ be a prime. How do we show that the number of reducible polynomials over $\mathbb{Z}_p$ of the form $x^2+ax+b$ is $p(p+1)/2$?

I just know that $\mathbb{Z}_p$ is a field, and a polynomial of the form $x^2+ax+b$ is of degree 2, so there is a theorem which says a polynomial of degree 2 or 3 is reducible over a field if and only if it has a root in that field.

So how can I show the total number of polynomials $x^2+ax+b$ which have a zero in $\mathbb{Z}_p$ is $p(p+1)/2$? Any help would be appreciated.
• October 10th 2010, 03:56 AM
tonio
Quote:

Originally Posted by demode
Let $p$ be a prime. How do we show that the number of reducible polynomials over $\mathbb{Z}_p$ of the form $x^2+ax+b$ is $p(p+1)/2$?

I just know that $\mathbb{Z}_p$ is a field, and a polynomial of the form $x^2+ax+b$ is of degree 2, so there is a theorem which says a polynomial of degree 2 or 3 is reducible over a field if and only if it has a root in that field.

So how can I show the total number of polynomials $x^2+ax+b$ which have a zero in $\mathbb{Z}_p$ is $p(p+1)/2$? Any help would be appreciated.

A polynomial $x^2+ax+b$ is reducible iff $x^2+ax+b=(x-\alpha)^2\,\,or\,\,x^2+ax+b=(x-\alpha)(x-\beta)\,,\,\alpha\neq \beta$ .

Of the first kind are there $p$ different pol's, and of the second kind are there $\frac{p(p-1)}{2}$ different pol's (why do we divide by 2?)

Tonio
• October 10th 2010, 10:57 PM
demode
Quote:

Originally Posted by tonio
A polynomial $x^2+ax+b$ is reducible iff $x^2+ax+b=(x-\alpha)^2\,\,or\,\,x^2+ax+b=(x-\alpha)(x-\beta)\,,\,\alpha\neq \beta$ .

Of the first kind are there $p$ different pol's, and of the second kind are there $\frac{p(p-1)}{2}$ different pol's (why do we divide by 2?)

Tonio

Could you please explain why you wrote that expression for the kind $(x-\alpha)(x-\beta)$? For the first kind there are p different polynomials because it is in $\mathbb{Z}_p$... but in for the second one I don't know why you wrote that expression and divided by 2...

but it is correct because $p + \frac{p(p-1)}{2} = \frac{p(p+1)}{2}$.
• October 11th 2010, 05:27 AM
tonio
Quote:

Originally Posted by demode
Could you please explain why you wrote that expression for the kind $(x-\alpha)(x-\beta)$? For the first kind there are p different polynomials because it is in $\mathbb{Z}_p$... but in for the second one I don't know why you wrote that expression and divided by 2...

but it is correct because $p + \frac{p(p-1)}{2} = \frac{p(p+1)}{2}$.

I wrote the expression for the second kind as I did because a quadratic pol. may have two different roots, and in the calculations I divided by two since $(x-\alpha)(x-\beta)=(x-\beta)(x-\alpha)$ ...

Tonio
• October 12th 2010, 04:31 AM
demode
The question further asks: "Determine the number of reducible quadratic polynomials over $\mathbb{Z}_p$".

I think again we need to consider the number of distinct expressions of the form $(x-c)(x-d)$.

I know that quadratic polynomials have the form $ax^2 + bx + c$. So this time we need to use the quadratic formula for the roots:

$\frac{-b \pm \sqrt {b^2-4ac}}{2a}$

but how could I find the number of reducible polynomials from this formula?
• October 12th 2010, 05:04 AM
tonio
Quote:

Originally Posted by demode
The question further asks: "Determine the number of reducible quadratic polynomials over $\mathbb{Z}_p$".

I think again we need to consider the number of distinct expressions of the form $(x-c)(x-d)$.

I know that quadratic polynomials have the form $ax^2 + bx + c$. So this time we need to use the quadratic formula for the roots:

$\frac{-b \pm \sqrt {b^2-4ac}}{2a}$

but how could I find the number of reducible polynomials from this formula?

You don't need that formula. Again, if a quadratic is red. then $ax^2+bx+c=a(x-\alpha)^2\,\,or\,\, =a(x-\alpha)(x-\beta)$ , and you make calculations very simmilar to the ones in the monic case.

Tonio
• October 12th 2010, 02:51 PM
demode
Quote:

Originally Posted by tonio
You don't need that formula. Again, if a quadratic is red. then $ax^2+bx+c=a(x-\alpha)^2\,\,or\,\, =a(x-\alpha)(x-\beta)$ , and you make calculations very simmilar to the ones in the monic case.

Tonio

So for the kind $ax^2+bx+c=a(x-\alpha)^2$ there are p different polynomials. Is this correct? or do I need to add another p to this?

and for the kind $a(x-\alpha)(x-\beta)$ there are $\frac{p(p-1)}{2} + p = \frac{p(p+1)}{2}$ polynomials. I added the p because "a" can be a root.

So in total $\frac{p(p+1)}{2} + p$ polynomials?

P.S. Isn't it also possible for the "a" in the first type to be different from the "a" in the second type?
• October 12th 2010, 09:32 PM
demode
$a(x-\alpha)^2$ or $a(x-\alpha)(x-\beta)$.

of the first kind there are $p+p=2p$ polynomials. And of the second kind there are $\frac{p(p-1)}{2} + p = \frac{p(p+1)}{2}$ polynomials.

So there are $2p + \frac{p(p+1)}{2} = \frac{p(p+5)}{2}$ in total.

Is this alright?
• October 13th 2010, 04:41 AM
tonio
Quote:

Originally Posted by demode
$a(x-\alpha)^2$ or $a(x-\alpha)(x-\beta)$.

of the first kind there are $p+p=2p$ polynomials.

No...the quadratic coefficient $a\in\mathbb{Z}_p$ cannot be zero, so for any choice of $\alpha\in\mathbb{Z}_p$ there are $p-2$ choices for $a$

(since 0 cannot be and you ALREADY counted $a=1$!).

Take it from here.

Tonio

And of the second kind there are $\frac{p(p-1)}{2} + p = \frac{p(p+1)}{2}$ polynomials.

So there are $2p + \frac{p(p+1)}{2} = \frac{p(p+5)}{2}$ in total.

Is this alright?

.
• October 14th 2010, 12:12 AM
demode
Oops, yes the quadratic coefficient can't be zero!

Previously we have shown that the number of reducible polynomials over $\mathbb{Z}_p$ of the form $x^2+ax+b$ are $p(p+1)/2$. So can we just make use of this result and deduce that the number of reducible quadratic polynomials $ax^2+bx+c$ is $(p-2) \frac{p(p+1)}{2}$?