How can I factor $x^{12}+x^{11}+\cdots+x+1$ in $\mathbb F_3[x]$?

Question

I can prove that $\mathbb F_3[x]$ is a UFD, so $f(x)=x^{12}+x^{11}+\cdots+x+1$ can be factored. And because neither 0, 1, nor 2 is a root of $f(x)$, all factors are more than 1 degrees.

But I don’t know how to factor $f(x)=x^{12}+x^{11}+\cdots+x+1$, or as another simple example, $g(x)=x^4+x^3+x+2$.

How do I find out factorizations of $f(x)$ and $g(x)$ in $\mathbb F_3[x]$?

Answer 1

$$x^4+x^3+x+2=x^4+x(x^2+1)-1=(x^2+1)(x^2+x-1).$$ $$x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1=$$ $$=x^{12}+x^{11}-2x^{10}-8x^9-5x^8+7x^7+16x^6+7x^5-5x^4-8x^3-2x^2+x+1=$$ $$=(x^3-x-1)(x^3+x^2-1)(x^3+x^2+x-1)(x^3-x^2-x-1).$$

Answer 2

Suppose $x$ is a root of $f$ in some extension field of $\mathbb{F}_3$; then $x$ is a 13th root of 1. Now $\mathbb{F}_{27}$ is the splitting field of $x^{27} - x$, and we see $x^{13} - 1$ divides $x^{27} - x$; therefore, each root of $f$ lies in $\mathbb{F}_{27}$. It follows that each irreducible factor of $f$ has degree 3.

Furthermore, for such a root $x$, we have $N_{\mathbb{F}_3}^{\mathbb{F}_{27}}(x) = x \cdot x^3 \cdot x^9 = 1$ since the Galois group consists of the identity, the Frobenius morphism $x \mapsto x^3$, and the square of the Frobenius morphism. Therefore, the irreducible factors would be of the form $x^3 + ax^2 + bx - 1$.

Conversely, for any element $y \in \mathbb{F}_{27} \setminus \mathbb{F}_3$ such that $N_{\mathbb{F}_3}^{\mathbb{F}_{27}}(y) = 1$, this implies $y^{13} = 1$; and since $y \ne 1$, this implies $f(y) = 0$. Therefore, every irreducible polynomial of the form $x^3 + ax^2 + bx - 1$ is in fact a factor of $f(x)$.

Now, to follow a comment by Servaes: since $x^3 + ax^2 + bx - 1$ is not allowed to have either $x=1$ or $x=-1$ as a root, that means that $a+b \ne 0$ and $a-b \ne 2$. That restriction leaves us with only four possibilities: $(a,b) \in \{ (0, -1), (1, 0), (1, 1), (-1, -1) \}$. Each of these is in fact irreducible since it is a cubic polynomial of degree 3 with no root in $\mathbb{F}_3$; and the product of these factors accounts for the full degree 12 of $f$.

In summary, we get $$f(x) = (x^3 - x - 1) (x^3 + x^2 - 1) (x^3 + x^2 + x - 1) (x^3 - x^2 - x - 1).$$

Answer 3

Let $K$ be a splitting field of $f$, and note that $f$ has no roots in $\Bbb{F}_3$ so in particular $K\neq\Bbb{F}_3$. Because $$(x-1)f(x)=x^{13}-1 \qquad\text{ and }\qquad (x^{13}-1)(x^{13}-1)x=x^{27}-x,$$ where the latter splits over $\Bbb{F}_{27}$, we see that $K$ is isomorphic to a subfield of $\Bbb{F}_{27}$, and hence isomorphic to $\Bbb{F}_{27}$ itself. This means the minimal polynomial of every root of $f$ has degree $3$, that is to say $f$ is a product of four irreducible cubic polynomials. Moreover, we see that $f$ is squarefree, so it is a product of four distinct monic irreducible cubic polynomials. There are only six such polynomials in $\Bbb{F}_3$, so pick one and see whether it divides $f$.

For $g$ a similar but simpler approach works; it has no roots in $\Bbb{F}_3$ so it is either irreducible or a product of two irreducible quadratics. There are only three irreducible quadratics in $\Bbb{F}_3[x]$, so this is even easier to check. On the other hand, a brute force check shows that if \begin{eqnarray*} x^4+x^3+x+2&=&(x^2+ax+b)(x^2+cx+d)\\ &=&x^4+(a+c)x^3+(ac+b+d)x^2+(ad+bc)x+bd, \end{eqnarray*} then $b=-d$ by comparing constant coefficients. Then the coefficient of $x^2$ shows that $ac=0$, so without loss of generality $a=0$, and then $c=1$ and $b=1$ and $d=2$ so $$g(x)=(x^2+1)(x^2+x+2).$$