• Dec 11th 2008, 01:02 PM
mandy123
Let p be a prime. Determine the number of irreducible quadratic polynomials over Z_p

(Worried)
• Dec 11th 2008, 08:07 PM
ThePerfectHacker
Quote:

Originally Posted by mandy123
Let p be a prime. Determine the number of irreducible quadratic polynomials over Z_p

The polynomial \$\displaystyle x^{p^2} - x\$ factors into a product of monic irreducible polynomials of order dividing \$\displaystyle 2\$.
There are \$\displaystyle p\$ linear monic polynomials. Let \$\displaystyle n\$ be the number of monic irreducible quadradic polynomials.
Then by counting degrees of polynomials in \$\displaystyle x^{p^2} - x = \prod_{\deg p(x) | 2}p(x)\$
We see that \$\displaystyle p + 2N = p^2 \implies N = \tfrac{1}{2}(p^2 - p)\$.

(This formula can be generalized to polynomials of degree \$\displaystyle m\$ by applying Mobius inversion formula)
• Dec 12th 2008, 07:22 AM
mandy123
So then what if p is not a prime, what if we are told to
Determine the number of irreducible quadratic polynomials over Z_p?
how would that change the answer?
• Dec 12th 2008, 08:28 AM
ThePerfectHacker
Quote:

Originally Posted by mandy123
So then what if p is not a prime, what if we are told to
Determine the number of irreducible quadratic polynomials over Z_p?
how would that change the answer?

Finite fields have orders of power of primes. Thus, your question would be to count the number of irreducible quadradics over \$\displaystyle \mathbb{F}_q\$ where \$\displaystyle q=p^n\$ (a power of prime). In this case the same theorem applies i.e. \$\displaystyle x^{q^2} - x\$ factors into monic irreducible polynomials having order dividing \$\displaystyle 2\$.