Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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). $$

share|improve this answer
    
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)
share|improve this answer
    
+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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.