Write $x^3 + 2x+1$ as a product of linear polynomials over some extension field of $\mathbb{Z}_3$

Question

Write $x^3 + 2x+1$ as a product of linear polynomials over some extension field of $\mathbb{Z}_3$

Long division seems to be taking me nowhere, If $\beta$ is a root in some extension then using long division one can write

$$x^3 + 2x+1 = (x-\beta) (x^2+ \beta x+ \beta^2 + 2)$$

Here is a similar question

Suppose that $\beta$ is a zero of $f(x)=x^4+x+1$ in some field extensions of $E$ of $Z_2$.Write $f(x)$ as a product of linear factors in $E[x]$

Is there a general method to approach such problems or are they done through trail and error method.

I haven't covered Galois theory and the problem is from field extensions chapter of gallian, so please avoid Galois theory if possible.

Answer 1

If you want to continue the way you started, i.e. with $$x^3 + 2x+1 = (x-\beta) (x^2+ \beta x+ \beta^2 + 2)$$ you can try to find the roots of the second factor by using the usual method for quadratics, adjusted for characteristic 3. I'll start it so you know what I mean:

To solve $x^2+ \beta x+ \beta^2 + 2=0$, we can complete the square, noting that $2\beta + 2\beta = \beta$ and $4\beta^2=\beta^2$in any extension of $\mathbb{Z}_3$ (since $4\equiv 1$). $$x^2+ \beta x+ \beta^2 + 2=(x+2\beta)^2 + 2=0$$ But this is easy now since this is the same as $$(x+2\beta)^2 = 1$$ which should allow you to get the remaining roots.

Answer 2

You can just apply the Frobenius automorphism to get the other roots :
If $\beta$ is a root of $x^3+2x+1$, then so are $\beta^3 = \beta+2$, and $\beta^9 = (\beta+2)^3 = (\beta+2)+2 = \beta+1$