# Number of irreducible polynomials over $\mathbb Z_p$ [duplicate]

This question already has an answer here:

How many irreducible polynomials over $\mathbb Z_p$ of the form $x^2+ax+b$ are there?

No idea.

## marked as duplicate by tomasz, Davide Giraudo, Martin, Erick Wong, SashaApr 13 '13 at 13:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• An irreducible polynomial of degree 2 must have no roots, and vice versa. – ronash Apr 13 '13 at 12:36
• Hint: First count the reducible ones. Or use the search engine, this was asked (for arbitrary degree) at least 10 times on math.SE. – Martin Brandenburg Apr 13 '13 at 12:37
• @MartinBrandenburg: if you were aware of that, why didn't you vote to close this question as duplicate? The arbitrary degree answer might be a little too complicated (what with Mobius function and all...), but the one I marked is a simple enough generalization. – tomasz Apr 13 '13 at 12:46

## 1 Answer

The formula is $$\frac{p^2 - p}{2}.$$ The reason is that the polynomial $$x^{p^{2}} - x$$ factors as the product of all the distinct irreducible, monic polynomials of degree dividing $2$, thus of degree $1$ or $2$, And there are $p$ monic polynomials of degree $1$.

More generally, $$x^{p^{d}} - x$$ factors as the product of all the distinct irreducible, monic polynomials of degree dividing $d$. In general, to recover the number of the irreducible, monic polynomials of degree $d$, you have to use Moebius inversion.