In a finite field there exists an irreducible polynomial of degree at least $n$ for $n \in \mathbb{N}$

Question

This question already has an answer here, but I'm looking for a solution that doesn't use field extensions. It's relatively easy to find a polynomial without zeros for every $n$ but as far as I know this doesn't imply that the polynomial is irreducible (maybe in a finite field it does?). Thank you for your answers.

Answer 1

Let $F$ be a finite field of characteristic $p$ and let $n\in\Bbb{N}$. Let $k$ be an integer coprime to $p$. Then the polynomial $x^k+1$ is separable over $F$, so it is a product of distinct irreducible factors. For any degree $d$ there are only finitely many (irreducible) polynomials of degree $d$ with coefficients in $F$, so for sufficiently large values of $k$ it must have an irreducible factor of degree $n$.

Answer 2

Hint use Euclid's idea: consider $1+p_1\cdots p_k$ where the $p_i$ are all irreducibles of degree $< n$