Primitive Root in Quotient Ring

Question

Find a primitive root of $R[x]/\langle x^4+x+2 \rangle$ where $R$ is the integers mod $3$.

Is there a good general stratagy to this sort of thing?

Answer 1

Your ring has $3^4=81$ elements. Since the polynomial $x^4+x+2$ is irreducible, hence the quotient ring forms a field. This means its unit group (the invertible elements) will be of order $80=2^4 \cdot 5$. For any element $\alpha$ to be a primitive root all you need is to check if $$\alpha^{80/q} \neq 1$$ for every prime divisor $q$ of $80$. This means all you need to do is to check if $$\alpha^{40} \neq 1 \text{ and } \alpha^{16} \neq 1$$

Answer 2

We are dealing with a finite field extension, provided the base ring $R$ is a finite field (it is) and the polynomial is irreducible over that field (also true in this case, although that is something to be verified). The units of that finite field extension (everything but the zero element) form an (abelian) multiplicative group. So a starting point is finding how big the multiplicative group is. Then we know what order the "primitive" elements are, i.e. have their powers generate all nonzero elements.

The order of the multiplicative group is $3^4 - 1 = 80$.

Since the multiplicative group is abelian, it helps to find elements $u,v$ whose orders are coprime, because the order of $uv$ would then be the product of the orders of $u$ and $v$.

A good starting point is to find out the order of the image of $x$ in the quotient ring/field extension of characteristic 3. Note that since $x^4 + x + 2 = 0$ there:

$$ x^4 = -x + 1 $$

From this we can work out the higher powers of $x$ as well, e.g. $x^5 = -x^2 + x$ and so on. The least natural power $k$ such that $x^k = 1$ will be the order of $x$.