Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How do I factorize a polynomial $X^n - 1$ over $\mathbb{F}_p$? In particular I need to find factors of the polynomial $X^{3^3 - 1} - 1 = X^{26} - 1$ over $\mathbb{F}_3$.

share|improve this question
4  
1  
For your example: Check that $p(X)=X^3+2X+1$ is an irreducible polynomial of a primitive element of $(\mathbb{F}_{27})^*$. To do that, see that the images of $1,X,\ldots,X^{25}$ in $\mathbb{F}_3[X]/(P(X))$ are all different. In the process, you'll get the coefficients of all field elements according to the basis $1,\alpha,\alpha^2$ of $\mathbb{F}_{27}/\mathbb{F}_3$, where $\alpha$ is the image of $X$. Now use the partition of $\mathbb{F}_{27}$ to orbits under the Galois group, generated by $x\mapsto x^3$, and multiply linear factors to get the irreducible polynomials. –  user2734 Feb 3 '10 at 23:17
1  
Abstract Algebra by Dummit and Foote has a section on finite fields (14.3) which should have all the info you need. –  Sonia Balagopalan Feb 3 '10 at 23:34
2  
What the heck does this have to do with Kummer theory? –  darij grinberg Feb 4 '10 at 10:21
2  
I guess I was wrong. –  Harry Gindi Feb 4 '10 at 15:50
show 2 more comments

3 Answers

up vote 9 down vote accepted

If you just need a quick answer (to decide if something else is going to work how you need), then you can do this with Wolfram|Alpha. Go there: http://www.wolframalpha.com/ and input "factor x^26-1" and press the "equal" button. It'll show some info about the polynomial, including the factors mod 2. In many boxes, there's a link for "Show More". Press the one attached to the factors over GF(2), and it'll show you the factors over GF(3). In this case, you get $$(x+1) (x+2) (x^3+2 x+1) (x^3+2 x+2) (x^3+x^2+2) (x^3+x^2+x+2) (x^3+x^2+2 x+1) (x^3+2 x^2+1) (x^3+2 x^2+x+1) (x^3+2 x^2+2 x+2).$$

Annoying to have "2" instead of "-1" in GF(3), but that's the price of having a machine do your work for you.

share|improve this answer
    
I tried countless variations on wolframalpha, but not "factor x^26-1". thank you –  Alexandru Moșoi Feb 10 '10 at 23:49
add comment

I describe how to do this generally in my answer to question #16457 about cyclotomic integers. However, in this particular problem you are probably supposed to use the fact that the divisors of $x^{p^n} - x$ over $\mathbb{F}_p$ are precisely the irreducible polynomials of degree dividing $n$.

share|improve this answer
add comment

This seems very much like homework to me, so I'll be brief. I assume that your $Z_p$ denotes the field with $p$ elements; I will call it $\mathbb{F}_p$ henceforth (lest it be confused with the ring $\mathbb{Z}_p$ of $p$-adic integers).

You want to factor the polynomial $X^{p^a-1}-1$ over $\mathbb{F}\_{p}$. Let us go into the field $\mathbb{F}_{p^a}$; what are the roots of the polynomial $X^{p^a-1}-1$ factor over there? Hence, which divisors does $X^{p^a-1}-1$ have over $\mathbb{F}_p$ ? Can any of them occur more than once?

share|improve this answer
    
Yes, it's part of a homework, but the factorization is already given at few.vu.nl/~jeu/Teaching/CC/Notes0.pdf (page 22). Unfortunately the provided factorization is wrong and I need the correct one to continue. –  Alexandru Moșoi Feb 3 '10 at 22:34
1  
@Alexandru: You are right, there is a typo, and the last factor should be $X^3+X^2-X+1$. –  Sonia Balagopalan Feb 3 '10 at 23:07
add comment

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.