# Irreducible polynomials

What is the number of irreducible polynomials, $p(x)$, of degree $2$ over $F_q$, $q=p^n$?

-
How many reducible ones are there? How many total? –  Jack Schmidt Apr 9 '11 at 3:56
You could just list all the quadratics and then verify whether or not any elements of the finite field are zeros –  WWright Apr 9 '11 at 4:07

Note that a polynomial of degree $2$ is "reducible" iff its roots are in the field. Let us count the reducible polynomials. First count the monic ones, for which the coefficient of $x^2$ is $1$ (then you can multiply your answer by $q-1$ to allow the coefficient of $x^2$ to vary).

So how many monic reducible polynomials of degree $2$ are there? If the roots are to be distinct, they can be chosen in $\binom{q}{2}$ ways. And there are in addition $q$ monic polynomials that have a double root. Now put all these facts together. Subtract your answer from the number $(q-1)(q)(q)$ of degree $2$ polynomials.

-

Here is a sketch of a solution that proceeds directly, instead of counting the complement. It has the serious disadvantage that it does not work in characteristic $2$. Also, it uses more machinery than the counting the complement approach, but perhaps it has some merit.

Look at the quadratic $ax^2+bx+c$. The coefficient $a$ can be chosen in $q-1$ ways. We will show that for every such choice, and every one of the $q$ possibilities for $b$, there are $(q-1)/2$ choices for $c$ that yield an irreducible quadratic.

The idea is that (for characteristic $\ne 2$) a suitably interpreted version of the quadratic formula gives the zeros, and that in particular the quadratic has no zero in the field precisely when the discriminant $b^2-4ac$ is not a square in the field.

So let $a$ be a fixed non-zero element, and let $b$ be arbitrary but fixed. As $c$ ranges over all the elements of the field, so does $b^2-4ac$. But exactly $(q-1)/2$ elements of the field are non-squares. This completes the argument.

-