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!
 A: 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.
A: 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. $$
