Results 1 to 10 of 10

Thread: Reducible Polynomials

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    225

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by demode View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2009
    Posts
    225
    Quote Originally Posted by tonio View Post
    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}$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by demode View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2009
    Posts
    225
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by demode View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Dec 2009
    Posts
    225
    Quote Originally Posted by tonio View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Dec 2009
    Posts
    225
    $\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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by demode View Post
    $\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?
    .
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Dec 2009
    Posts
    225
    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}$?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Reducible
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Nov 10th 2010, 06:35 PM
  2. [SOLVED] Reducible Equations
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: Jul 14th 2010, 03:56 AM
  3. Reducible problem. Help!
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Apr 18th 2010, 02:33 AM
  4. reducible and irreducible
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Mar 21st 2010, 09:33 PM
  5. R[x] - Reducible?
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Oct 18th 2009, 08:27 PM

Search Tags


/mathhelpforum @mathhelpforum