Polynomials with no solution in polynomial ring $( \mathbb Z / p \mathbb Z)[x]$ [duplicate]

How can I show that for any prime $p$ and any $d\ge 2$ there exists a polynomial of degree $d$ in $\mathbb{F}_p[X]$ with no roots? ($\mathbb{F}_p$ is the finite field with $p$ elements). Thanks in advance for any idea.

Even more than that, there exists an irreducible polynomial of degree $d$. The field $\mathbb{F}_{p^d}$ is a field extension of degree $d$ over $\mathbb{F_p}$. The multiplicative group a finite field is cyclic, so let $\alpha$ be a generator of $\mathbb{F}_{p^d}^{\times}$, and then we have $\mathbb{F}_{p^d}=\mathbb{F}_p(\alpha)$. Since $[\mathbb{F}_p(\alpha):\mathbb{F}_p]=d$ it follows that the minimal polynomial of $\alpha$ is an irreducible polynomial in $\mathbb{F}_p[x]$ of degree $d$.

Note that $f(x)=x^d-x$ has at least two roots in $\Bbb Z/p\Bbb Z$, namely $0$ and $1$. Thus, viewed as a map $f\colon\Bbb Z/p\Bbb Z\to \Bbb Z/p\Bbb Z$, it is not injective, hence also not surjective. Pick $a\in \Bbb Z/p\Bbb Z$ that is not in the image. Then $g(x):=x^d-x-a$ has no root in $\Bbb Z/p\Bbb Z$.

You can even find an irreducible polynomial of degree $d$.

The field $F_{p^d}$ has characteristic $p$, hence it can be viewed as an extension of $F_p$ with degree $d$.

By the primitive element theorem, there exists some $\alpha \in F_{p^d}$ such that $F_{p^d}=F_p(\alpha)$. Call $M$ the minimal polynomial of $\alpha$. Then $M$ is irreducible, the ring $F_p[\alpha]$ is isomorphic to $F_p[X]/(M)$, which is a field, hence $$F_p[X]/(M) \simeq F_p[\alpha]=F_p(\alpha)=F_{p^d}.$$ https://en.wikipedia.org/wiki/Primitive_element_theorem

As a result, the polynomial $M$ is irreducible with degree $d$.

Remarks : there exists a formula providing the number of irreducible with degree $d$ on $F_p$.

For any $\alpha \in \mathbb F_p$ there are $p^{d-1}$ monic polynomials of degree $d$ that vanish at $\alpha$. This would give a maximum of $\lvert \mathbb F_p \rvert \cdot p^{d-1} = p^d$ polynomials with a root in $\mathbb F_p$, which is too weak a bound. However, we counted polynomials with $k$ roots in $\mathbb F_p$ $k$ times and such a polynomial certainly exist for some $k \geq 2$. Therefore the number of monic polynomials with a root in $\mathbb F_p$ is strictly less than $p^d$. In other words, there must be a polynomial of degree $d$ without roots in $\mathbb F_p$.

This answer presents another approach to show that irreducible polynomials of any degree exist. It is purely based on counting arguments that can be derived without (and in fact predate) the theory of splitting fields.

Fix a prime $p$ and let $A_n$ for $n\geq 1$ be the number of irreducible monic polynomials of degree $n$ in $\mathbb F_p[x]$. The following expression for $A_n$ dates back to Gauss and Dedekind:

$$n A_n = \sum_{d \mid n} \operatorname{\mu}\left(\frac n d \right) p^d$$

where $\mu$ is the Möbius function. Since $\mu$ takes values in $\{-1,0,1\}$ and $\mu(1)=1$ this shows that $A_n>0$ for all $n\geq 1$. The formula above is the Möbius inversion (already known to Dedekind) of $$p^n = \sum_{d \mid n} d A_d.$$ This also suffices to show that $n A_n > 0$ since the summands for $d < n$ are too small to sum to $p^n$ (using the bound $d A_d \leq p^d$). This second identity in turn follows from counting the number of ways in which irreducible polynomials can be multiplied to give all polynomials of a given degree which leads to the “generating” identity $$\prod_{n=1}^{\infty}(1-x^n)^{A_n} \equiv 1-px \pmod {x^m}$$ for any $m \geq 1$.