# Reducible Polynomials

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

I just know that $\displaystyle \mathbb{Z}_p$ is a field, and a polynomial of the form $\displaystyle 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 $\displaystyle x^2+ax+b$ which have a zero in $\displaystyle \mathbb{Z}_p$ is $\displaystyle p(p+1)/2$? Any help would be appreciated.
• Oct 10th 2010, 03:56 AM
tonio
Quote:

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

I just know that $\displaystyle \mathbb{Z}_p$ is a field, and a polynomial of the form $\displaystyle 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 $\displaystyle x^2+ax+b$ which have a zero in $\displaystyle \mathbb{Z}_p$ is $\displaystyle p(p+1)/2$? Any help would be appreciated.

A polynomial $\displaystyle x^2+ax+b$ is reducible iff $\displaystyle 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 $\displaystyle p$ different pol's, and of the second kind are there $\displaystyle \frac{p(p-1)}{2}$ different pol's (why do we divide by 2?)

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

Originally Posted by tonio
A polynomial $\displaystyle x^2+ax+b$ is reducible iff $\displaystyle 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 $\displaystyle p$ different pol's, and of the second kind are there $\displaystyle \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 $\displaystyle (x-\alpha)(x-\beta)$? For the first kind there are p different polynomials because it is in $\displaystyle \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 $\displaystyle p + \frac{p(p-1)}{2} = \frac{p(p+1)}{2}$.
• Oct 11th 2010, 05:27 AM
tonio
Quote:

Originally Posted by demode
Could you please explain why you wrote that expression for the kind $\displaystyle (x-\alpha)(x-\beta)$? For the first kind there are p different polynomials because it is in $\displaystyle \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 $\displaystyle 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 $\displaystyle (x-\alpha)(x-\beta)=(x-\beta)(x-\alpha)$ ...

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

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

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

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

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

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

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

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

$\displaystyle \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 $\displaystyle 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
• Oct 12th 2010, 02:51 PM
demode
Quote:

Originally Posted by tonio
You don't need that formula. Again, if a quadratic is red. then $\displaystyle 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 $\displaystyle 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 $\displaystyle a(x-\alpha)(x-\beta)$ there are $\displaystyle \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 $\displaystyle \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?
• Oct 12th 2010, 09:32 PM
demode
$\displaystyle a(x-\alpha)^2$ or $\displaystyle a(x-\alpha)(x-\beta)$.

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

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

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

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

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

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

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

Take it from here.

Tonio

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

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

Is this alright?

.
• Oct 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 $\displaystyle \mathbb{Z}_p$ of the form $\displaystyle x^2+ax+b$ are $\displaystyle p(p+1)/2$. So can we just make use of this result and deduce that the number of reducible quadratic polynomials $\displaystyle ax^2+bx+c$ is $\displaystyle (p-2) \frac{p(p+1)}{2}$?