Does there always exist an irreducible polynomial of degree $d$ over $\mathbb{Z}/p\mathbb{Z}$?

Question

Let $p$ be a prime and let $d$ be a positive integer. Does there always exist an irreducible (i.e. unfactorable) polynomial of degree $d$ over $\mathbb{Z}/p\mathbb{Z}$?

Answer 1

This is a good question, because it is not obvious that the answer is yes. This is wrong if you ask the same question with $\Bbb R$ instead of $\Bbb F_p := \Bbb Z/p\Bbb Z$, because irreducible polynomials over $\Bbb R$ have degree $≤2$.

Here is a theoretical way to see the existence of an irreducible polynomial of degree $d$. Consider an algebraic closure $K$ of $\Bbb F_p$. The set of the roots of $f(X)=X^{p^d}-X$ in $K$, i.e. $$E = \{x \in K \mid x^{p^d}=x \}$$ happens to be a field$^{(1)}$, which is an extension of $\Bbb F_p$. Its cardinality is exactly $p^d$, because $f$ has no multiple roots (for instance $(f,f')=(X^{p^d}-X,-1)=1$).

The multiplicative group $E^*$ of the finite field $E$ is cyclic, generated by $a$, say. Consider the minimal polynomial of $a$ over $\Bbb F_p$. Since $E = \Bbb F_p(a)$, it has degree $d$, because the dimension of $E$ over $\Bbb F_p$ is $d$, since $|E|=p^d=p^{\text{dim }_{{\Bbb F}_p}(E)}$. Finally, being a minimal polynomial, it is irreducible. QED. $\qquad\blacksquare$

---

$^{(1)}$Clearly, $0,1 \in E$. If $0 ≠ x \in E$, then $x^{-1} \in E$. If $x,y \in E$ then $xy \in E$. The only difficult point is to understand why $x,y \in E$ then $x+y \in E$. This is because $(x+y)^{p}=x^p+y^p$ holds! Actually, you use Newton's binomial formula, and all of the binomial coefficients vanish ($p$ being a prime number), but the first and the last one – see Frobenius' endomorphism. Therefore $(x+y)^{p^d}=((((x+y)^{p})^{p})^{\ldots})^p=x^{p^d}+y^{p^d}$, so that $(x+y)^{p^d}=x+y$ provided that $x^{p^d}=x$ and $y^{p^d}=y$.