How to factor $X^{20}-1$ in $\mathbb{F}_3[X]$

Question

I am trying to factor $X^{20}-1$ into irreducible polynomials in $\mathbb{F}_3[X]$. The first thing I saw is that $1$ is a root. Second, $-1$ must be one too. I have taken the derivative $20X^{19}$ to convince myself that these roots are single. The next thing I could try to do is rewriting $X^{20}-1$ as $$ (X^2-1)(X^{18}\pm X^{17}\pm X^{16} \cdots +1) $$ (There must be some sequence of $+$ and $-$ that satisfy that equality.) I thought that the polynomial below would work: $$ g(X) = X^{18} + X^{16} + X^{14} + \cdots +X^2+1 $$ Now, if $$ f(X) = 1 + X + X^2 + \cdots + X^9 $$ we have that $\ f(X^2) = g(X) \ $. The polynomial $f(X)$ looks nice but I need some advice to go on from here. I hope that you can tell me if there is some helpful theorem that I should use.

Answer 1

Before reduction mod $3$, just using factorizations of $X^n\pm1$:

$$\begin{align} &\phantom{{}={}}X^{20}-1 \\ & = (X^{10}+1)(X^{10}-1)\\ &=(X^{10}+1)(X^5+1)(X^5-1)\\ &=(X^{10}+1)(X^5+1)(X^4+X^3+X^2+X+1)(X-1)\\ &=(X^{10}+1)(X+1)(X^4-X^3+X^2-X+1)(X^4+X^3+X^2+X+1)(X-1)\\ &=(X^2+1)(X^8-X^6+X^4-X^2+1)(X+1)(X^4-X^3+X^2-X+1)(X^4+X^3+X^2+X+1)(X-1)\\ \end{align}$$

The quadratic factor has no root mod $3$, so it is irreducible. The two quartic and single degree $8$ factors may reduce more mod $3$ though. None of them have roots mod $3$ by inspection, so if the quartics factor, they factor as the product of two irreducible quadratics. Of the $3^2$ monic quadratics, $3+\binom{3}{2}$ of them are reducible. That leaves precisely three irreducible monic quadratics: $X^2+1$, $X^2+X+2$, and $X^2+2x+2$. The first of these cannot be involved in the factorization of our two quartics when considering the constant term, so we examine $$\begin{align} \left(X^2+X+2\right)^2&=X^4+2X^3+5X^2+4X+4\\ \left(X^2+X+2\right)\left(X^2+2x+2\right)&=X^4+3X^3+6X^2+4X+4\\ \left(X^2+2x+2\right)^2&=X^4+4X^3+8X^2+8X+4\\ \end{align}$$ and none of these reduce to the quartic factors we have.

It remains to see if the degree eight factor can be split. Symmetry and the prime factorization of $8$ suggests that maybe it is worth examining if it can be split as $(X^4+\cdots\pm1)(X^4+\cdots\pm1)$. If it could, then we can deduce bit by bit what the coefficients would be:

$$\begin{align} X^8-X^6+X^4-X^2+1&\equiv(X^4+\cdots\pm1)(X^4+\cdots\pm1)\\ &\equiv(X^4+aX^3+\cdots\pm1)(X^4+\cdots\pm1)\\ &\equiv(X^4+aX^3+\cdots\pm1)(X^4-aX^3+\cdots\pm1)\\ &\equiv(X^4+aX^3+bX^2+\cdots\pm1)(X^4-aX^3+\cdots\pm1)\\ &\equiv(X^4+aX^3+bX^2+\cdots\pm1)(X^4-aX^3+(-1-b+a^2)X^2+\cdots\pm1)\\ \end{align}$$

Without loss of generality, $a$ is either $1$ or $0$. We lean toward $1$, since $0$ seems to make the factors sparse.

$$\begin{align} X^8-X^6+X^4-X^2+1&\equiv(X^4+X^3+bX^2+\cdots\pm1)(X^4-X^3-bX^2+\cdots\pm1)\\ &\equiv(X^4+X^3+bX^2+cX\pm1)(X^4-X^3-bX^2+\cdots\pm1)\\ &\equiv(X^4+X^3+bX^2+cX\pm1)(X^4-X^3-bX^2+(-c+2b)X\pm1)\\ \end{align}$$

So far this balances terms of degree at least $5$. To make the degree $1$ terms balance we would need $(-c+2b)+c\equiv0$. That is, we'd need $b\equiv0$.

$$\begin{align} X^8-X^6+X^4-X^2+1&\equiv(X^4+X^3+cX\pm1)(X^4-X^3-cX\pm1)\\ \end{align}$$

Now to balance degree $4$ terms, we have $\pm1-c-c\pm1=1$. That is, $c=1\mp2$.

$$\begin{align} X^8-X^6+X^4-X^2+1&\equiv(X^4+X^3+(1\mp2)X\pm1)(X^4-X^3-(1\mp2)X\pm1)\\ \end{align}$$

Degree $3$ terms are now balanced. To balance degree $2$ terms, we have $-(1\mp2)^2=-1$, which implies we need to use the upper sign from the $\pm$ and $\mp$ signs. We have propositioned that

$$\begin{align} X^8-X^6+X^4-X^2+1&\equiv(X^4+X^3-X+1)(X^4-X^3+X+1)\\ \end{align}$$

and now can check that this factorization is valid. These quartics still have no roots and do not split further under the same analysis that we applied to the earlier quartics. So we now have a complete factorization mod $3$. Rearranged in descending order of degrees of factors:

$$\begin{align} X^{20}-1 &\equiv(X^4+X^3-X+1)(X^4-X^3+X+1)(X^4-X^3+X^2-X+1)(X^4+X^3+X^2+X+1)(X^2+1)(X+1)(X-1)\\ \end{align}$$

Answer 2

This is how I would handle the troublesome factor $$ \Phi_{20}(x)=x^8-x^6+x^4-x^2+1. $$ The other factors that we get from the factorization of cyclotomic polynomials over $\Bbb{Z}$ remain irreducible but this cannot.

Let $\zeta$ a primitive root of order twenty in some extension field $L$ of $\Bbb{F}_3$ (as explained in the comments we must have $L=\Bbb{F}_{81}$, but that is immaterial even though it does tell us that the factors will be quartic). Galois theory tells us that the other roots of the minimal polynomial $m(x)$ of $\zeta$ are gotten by applying the Frobenius map $F(u)=u^3$ repeatedly. Thus they are $$ F(\zeta)=\zeta^3,\quad F(\zeta^3)=\zeta^9,\quad F(\zeta^9)=\zeta^{27}=\zeta^7. $$ The list ends here, because $F(\zeta^7)=\zeta^{21}=\zeta$. Therefore $$ m(x)=(x-\zeta)(x-\zeta^3)(x-\zeta^9)(x-\zeta^7)\in\Bbb{F}_3[x]. $$ We can immediately calculate that the constant term here is $$ \zeta\cdot\zeta^3\cdot\zeta^9\cdot\zeta^7=\zeta^{20}=1. $$ The other factor of $\Phi_{20}(x)$ must be $$ \overline{m}(x)=(x-\zeta^{11})(x-\zeta^{13})(x-\zeta^{17})(x-\zeta^{19}), $$ as these are the remaining primitive roots of order $20$.

But we know that $\zeta^{10}=-1$. Therefore the roots of $\overline{m}(x)$ are the negatives of the zeros of $m(x)$. In other words $$ \overline{m}(x)=m(-x). $$ Furthermore, the roots of $\overline{m}(x)$ are also the multiplicative inverses of the roots of $m(x)$. For its part this implies that $\overline{m}(x)$ is the reciprocal polynomial of $m(x)$, i.e. $\overline{m}(x)=x^4m(1/x).$

So, if $$ m(x)=x^4+ax^3+bx^2+cx+1, $$ then $$ x^4-ax^3+bx^2-cx+1=m(-x)=\overline{m}(x)=x^4m(\frac1x)=x^4+cx+bx^2+ax+1. $$ So we can deduce that we must have $c=-a$. The two remaining unknown coefficients, $a$ and $b$ can be solved by expanding the factorization $$ \begin{aligned} (x^8-x^6+x^4-x^2+1)&=(x^4+ax^3+bx^2-ax+1)(x^4-ax^3+bx^2+ax+1)\\ &=x^8+(2b-a^2)x^6+(2+b^2+2a^2)x^4+(2b-a^2)x^2+1. \end{aligned} $$ We see that $a=0$ would lead to $b=1$ (sixth degree term), which is not compatible with the quartic term. Thus $a\neq0$, so $a=\pm1$. Because instead of $\zeta$ we might as well have chosen $\zeta^{-1}$ the sign of $a$ is arbitrary, and w.l.o.g. we can set $a=1$. This forces $b=0$, so the factorization is $$ \Phi_{20}(x)=(x^4+x^3-x+1)(x^4-x^3+x+1) $$ which is also confirmed by Mathematica, Maple, and Alex Jordan :-)