Irreducible polynomials of degree greater than 4 over finite fields

Find the irreducible quadratics. Multiply them together. Those fourth degree polynomials won't do. Now try some others at random (or systematically, following a list in some natural order). When you find one with no roots you're done.

This is mildly tedious, but you'll get good at the arithmetic, which may come in handy in other computations in the future.

You can also ask Wolfram alpha to factor polynomials modulo $3$.

Since $3$ is a primitive root modulo $5$, the fifth roots of unity are in ${\bf F}_{81}$, but not in a proper subfield. This means that the cyclotomic polynomial $\Phi_5(X)=X^4+X^3+X^2+X+1$ is irreducible modulo $3$.

The elements of $GF(p^n)$ are the zeros of the polynomial $x^{p^n}-x$. This polynomials decomposes into irreducible polynomials of degree $d$ over $GF(p)$ where $d$ divides $n$. It can be shown that this decomposition contains at least one polynomial of degree $n$ which ensures the existence of a finite field with $p^n$ elements. In a CAS you usually have access to such irreducible polynomials.