Find an element of order $5$ of the field $\mathbb{Z}_3[x]/\langle x^4 + x + 2 \rangle$. Find an element of order $5$ of the field $\mathbb{Z}_3[x]/\langle x^4 + x + 2 \rangle$.
I tried the systematic method of considering
$$1=(ax^3 + bx^2 + cx + d)^5$$
and using the relation $x^4 = 2x+1$ but the algebra got messy. Any idea?

It is maybe good to know that the one or the other computer algebra system can deal systematically with computations in finite fields.
For instance, using sage, a small dialog with the sage interpreter detects all elements of multiplicative order $=5$, the code has a digestible mathematical syntax, that will be explained in the sequel:
sage: R.<X> = PolynomialRing( GF(3) )
sage: F.<x> = GF( 3^4, modulus=X^4+X+2 )

sage: F.multiplicative_generator()
x
sage: F.multiplicative_generator().multiplicative_order()
80

sage: for k in [ 16, 32, 48, 64 ]:
....:     print ( "x^%s = %s is an element of multiplicative order %s"
....:             % (k, x^k, (x^k).multiplicative_order() ) )
....:     
....:     
x^16 = 2*x^3 + x + 2 is an element of multiplicative order 5
x^32 = x^3 + 2*x^2 + 2 is an element of multiplicative order 5
x^48 = 2*x^2 + 2*x + 2 is an element of multiplicative order 5
x^64 = 2*x^2 + 2 is an element of multiplicative order 5

sage: [ y for y in F if not y.is_zero() and y.multiplicative_order() == 5 ]
[2*x^3 + x + 2, x^3 + 2*x^2 + 2, 2*x^2 + 2*x + 2, 2*x^2 + 2]

We have solved twice, without complications...
Comments for the code. Above, we have first initialized the ring $R=\Bbb F_3[X]$, since we need the "modulus" $X^4+X+2$, we construct $F=\Bbb F_3[X]/(X^4+X+2)$, this is a field with $3^4=81$ elements, then the group of its non-zero elements (with the multiplication) is a group of order $80$, it is cyclic, a generator is $x$, given by sage. (Of course, $y^{80}=1 for all $y\in F$, $y\ne 0$.)
Knowing it, we expect that all elements of order $5$ are of the shape
$$
x^{16k}\ ,\qquad k=1,2,3,4\ .
$$
The code asks for the explicit representation of these elements, checks also their multiplicative order.
One can also use the one-liner [ y for y in F if not y.is_zero() and y.multiplicative_order() == 5 ] to get them in an unstructural way.
Not needed, but to do something concrete in the direction of a human effort, let us check for instance (humanly) that the last element, $2(x^2+1)=-(x^2+1)$ has order $5$, computations get simpler if we use the Frobenius, so...
$$
\begin{aligned}
(-(x^2+1))^5
&=-(x^2+1)^5
=(?)\ ,
\\
&\qquad\text{ so let us start with a related expression}\dots
\\[2mm]
(x^2+1)^6
&=(x^2+1)^3(x^2+1)^3
\\
&=(x^6+1)(x^6+1)
\\
&=x^{12}-x^6+1
\\
&=(x^4)^3-x^4\cdot x^2+1
\\
&=(1-x)^3-(1-x)\cdot x^2+1
\\
&=(1-x^3)-(x^2-x^3)+1
\\
&=-(x^2+1)\ ,\qquad\text{ so}
\\[2mm]
-(x^2+1)^5 
&= 
1\ .
\end{aligned}
$$
