Factor $x^{80} - 1$ over $F_3$
Effort
Factor $x^{80} - 1$ over $F_3$
$$\begin{aligned} x^{40}-1&=(x^{20}+1)(x^{20}-1) \\&=(x^{20}+1)(x^{10}+1)(x^{10}-1 ) \\&=(x^{20}+1)(x^{10}+1)(x^{5}+1 )(x^{5}-1 ) \end{aligned} $$
since we are in $F_3$ , $(x^{20}+1),(x^{10}+1),(x^{5}+1 )$ are factorable by $(x-2)$ and $x^5-1$ by $x-1$
so $$x^5-1= (x-1)(x^4+x^3+x^2+x+1) $$ what computer is saying that it factors to
(x + 1) * (x + 2) * (x^2 + 1) * (x^2 + x + 2) * (x^2 + 2*x + 2) * (x^4 +
x + 2) * (x^4 + 2*x + 2) * (x^4 + x^2 + 2) * (x^4 + x^2 + x + 1) * (x^4
+ x^2 + 2*x + 1) * (x^4 + 2*x^2 + 2) * (x^4 + x^3 + 2) * (x^4 + x^3 +
2*x + 1) * (x^4 + x^3 + x^2 + 1) * (x^4 + x^3 + x^2 + x + 1) * (x^4 +
x^3 + x^2 + 2*x + 2) * (x^4 + x^3 + 2*x^2 + 2*x + 2) * (x^4 + 2*x^3 + 2)
* (x^4 + 2*x^3 + x + 1) * (x^4 + 2*x^3 + x^2 + 1) * (x^4 + 2*x^3 + x^2 +
x + 2) * (x^4 + 2*x^3 + x^2 + 2*x + 1) * (x^4 + 2*x^3 + 2*x^2 + x + 2)
Been trying to find examples. I do not see the factors just how one would hypothetically find them. I think finding them takes a lot of work for a human. maybe it factors to something simple,beautiful and elegant but it does not seems to be the case unless I am wrong.
Note that $x^{81}-x = x(x^{80}-1)$. $81 = 3^4$, so $x^{81}-x$ factors into all the irreducible polynomials of degree $1,2,4$ over $\mathbb{F}_3$. So we could do this by listing polynomials of degrees $1,2,4$ and discovering which are irreducible.