# Number of irreducible polynomials of degree $3$ over $\mathbb{F}_3$ and $\mathbb{F}_5$.

I'm trying to find the number of $3$rd degree irreducible polynomials over $\mathbb{F}_3$ and $\mathbb{F}_5$.

Since a $3$rd degree polynomial is irreducible if and only if it is divisible by a $1$st degree polynomial, my strategy is to count the number of $3$rd degree polynomials and subtract the number of reducible ones.

I have figured that the number of $3$rd degree polynomials over a finite field $\mathbb{F}_q$ is $$(q-1)(q^3)=q^4-q^3,$$ but I'm having trouble figuring out how many of these are reducible. I'm having trouble with this, because just counting linear factors doesn't work, i.e. $$3x*4x=12x^2=2x^2=2x*x$$

in $\mathbb{F}_5$ (by the way, how does this not contradict $F[x]$ being a UFD?)

Thank you!

-
Ordinarily, people count monic polynomials. Is that what you have in mind? –  Lubin Apr 4 '13 at 0:19
No, I need to count all irreducible polynomials. –  William Stagner Apr 4 '13 at 0:20
Uniqueness of factorization is always described or defined up to units of the ring in question. Here, the units of $k[x]$ are the constants of $k$. So God’s in his heaven, all’s right with the world. –  Lubin Apr 4 '13 at 0:22
Okay, that makes sense. Then I have no idea how to count the reducible polynomials by linear factors... –  William Stagner Apr 4 '13 at 0:25
Since I can multiply any irreducible polynomial by the inverse of its leading coefficient to get a monic irreducible polynomial, then the number of irreducibles is the number of monic irreducibles multiplied by the order of the field - 1, right? –  William Stagner Apr 4 '13 at 0:36

This is a question that comes up over and over again; with the right search skills you and I could both find earlier related questions on SE. The idea is this, though: First, I'll count monics only. A monic irreducible of degree three has for its roots three conjugate irrationalities. Any one of these generates the field of cardinality $p^3$ — for our constant field we’re taking $\mathbb F_p$ for $p=3,5$. In that field of cardinality $p^3$, $p$ of them are already in $\mathbb F_p$. So there are $p^3-p$ cubic irrationalities in $\mathbb F_{27}$ and $\mathbb F_{125}$, respectively. In both cases, you divide by $3$ to get the number of monic irreducibles of degree $3$. Now just multiply by $p-1$ to count all the irreducibles.

The story gets both more complicated and more interesting if you want to count, say, irreducibles of degree $6$, but I’ll leave that to others, whose answers in any case will be more complete and more succinct than mine.

-
Thank you for the reply! Could you explain why you divide by $p^3-p$ by $3$ to obtain the number of monic irreducible polynomials? –  William Stagner Apr 4 '13 at 1:21
Because if $\alpha$, $\beta$, and $\gamma$ make up a set of conjugates, then $(x-\alpha)(x-\beta)(x-\gamma)$ is a polynomial with coeffs in $\mathbb F_p$, necessarily irreducible. So the set of all conj. triples can be looked at as the same as the set of monic irreds of deg $3$, and there are $N/3$ triples, if $N$ is the number of cubic irrationalities in the $\mathbb F(p^3)$ –  Lubin Apr 4 '13 at 13:04

The total number of irreducible polynomials of degree $n$ over a field $\mathbb{F}_p$ is

$$\psi(n)=\frac{p-1}{n}\sum_{d|n}\mu(d)p^{n/d}$$ where $\mu(n)$ is the Möbius function $$\mu(n) = \left\{ \begin{array}{ll} 1 & \mbox{if n=1};\\ 0 & \mbox{if n is a square};\\ (-1)^r & \mbox{if n has r distinct prime factors } .\end{array} \right.$$

-
Thank you for the answer! Unfortunately, we haven't proved this fact yet, so I don't think I'm able to use it. –  William Stagner Apr 4 '13 at 1:06
@ThomasAndrews you're right, I knew I was forgetting a factor somewhere. I fixed it now –  Brent J Apr 4 '13 at 1:17
@WilliamStagner perhaps you can just use it to double check your work then... –  Brent J Apr 4 '13 at 1:18
This is such a neat result, I always tried to slip it in when I was teaching abstract algebra. –  Lubin Apr 4 '13 at 13:23