# Factorize polynomial over $GF(3)$

I want to factorize $x^{11}-1$ over $GF(3)$ but I'm stuck at $(x-1)(x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1).$ I have tried to do it trial and error but failed. Is $$x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1$$ already irreducible over $GF(3)$?

-

The polynomial $$\phi_{11}(x):=\frac{x^{11}-1}{x-1}=\sum_{i=0}^{10}x^i\in GF(3)[x]$$ is not irreducible. Because $11\mid 3^5-1=242$, there is a primitive eleventh root of unity in the field $GF(3^5)$. This is a quintic extension field of $GF(3)$, so the minimal polynomials of all the primitive eleventh roots of unity are of degree $5$. Thus $\phi_{11}(x)$ must be a product of two irreducible quintic factors.

Finding the factors takes a bit of work. We repeatedly use the fact that, if $\beta$ is a root of a polynomial $f(x)\in GF(3)[x]$, then so is its image $F(\beta)=\beta^3$ under the Frobenius automorphism. Let $\alpha$ be one of the roots of $\phi_{11}(x)$. It has conjugates $F(\alpha)=\alpha^3$, $F(\alpha^3)=\alpha^9$, $F(\alpha^9)=\alpha^{27}=\alpha^5$ (here we use the fact that $\alpha^{11}=1$, so as $27=2\cdot11+5$ we get $\alpha^{27}=\alpha^5$) and $F(\alpha^5)=\alpha^{15}=\alpha^4$ (same trick). We can stop here as $F(\alpha^4)=\alpha^{12}=\alpha$, so we won't get any more conjugates ($F$ generates the relevant Galois group). Therefore the minimal polynomial of $\alpha$ is $$m_{\alpha}(x)=(x-\alpha)(x-\alpha^3)(x-\alpha^9)(x-\alpha^5)(x-\alpha^4)=x^5+ax^4+cx^3+bx^2+dx+e\in GF(3)[x].$$ The other eleventh roots of unity are the reciprocals of these, so $$m_{1/\alpha}(x)=(x-\alpha^{10})(x-\alpha^8)(x-\alpha^2)(x-\alpha^6)(x-\alpha^7),$$ and $$\phi_{11}(x)=m_{\alpha}(x)m_{1/\alpha}(x)$$ is the desired factorization.

Let us next compute the coefficient $e=(-1)^5\alpha\cdot\alpha^3\cdot\alpha^9\cdot\alpha^5\cdot\alpha^4=-\alpha^{22}=-1$. To make further progress, we use the fact that the roots of $m_{1/\alpha}(x)$ are the reciprocals of the roots of $m_{\alpha}(x)$. Thus the polynomial $x^5m_{\alpha}(1/x)=ex^5+dx^4+cx^3+bx^2+ax+1$ has the same roots (with the same multiplicities) as $m_{1/\alpha}(x)$, so they must be scalar multiples of each other. Taking into account the known constant term $e=-1$ we get $$m_{1/\alpha}(x)=x^5-dx^4-cx^3-bx^2-ax-1.$$ There are four unknowns $a,b,c,d\in GF(3)$. We get a bunch of equations tying these together by expanding $m_{\alpha}(x)m_{1/\alpha}(x)=\phi_{11}(x)$. There may be a systematic way of solving the resulting system, but I took the easy way out, and guessed $a=0$ (there are three possible values of $a$, so guessing won't take much time). This leads to a solution $d=-1$, $b=-1$, $c=1$ and to the factorization $$\phi_{11}(x)=(x^5-x^3+x^2-x-1)(x^5+x^4-x^3+x^2-1).$$

-
Hi, are the 2 irreducible quintic factors distinct? Even with the clue that they are quintic, I still can't find the factors. Is there a way to find the factors? – newbowl Apr 14 '12 at 13:28
@newbowl: I just worked that out. They must be distinct and reciprocal polynomials of each other, because between them they must have a total of ten distinct roots. – Jyrki Lahtonen Apr 14 '12 at 13:39

I don't want at all to depreciate the cleverness and the mastery of the previous answer, however, you should be aware that this kind of questions – it is hard to define what is this kind, it grows every day – can be answered by computer algebra. For example, using sage :

sage: R.<x> = PolynomialRing(GF(3))
sage: factor(x^11 - 1)
(x + 2) * (x^5 + 2*x^3 + x^2 + 2*x + 2) * (x^5 + x^4 + 2*x^3 + x^2 + 2)

-
+1: Worth remembering. I knew that I could have the answer quicker with Mathematica, but I wanted to check, whether there would be an easy way of seeing it. I'm not happy with my solution. – Jyrki Lahtonen Apr 14 '12 at 17:17