MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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
What the heck does this have to do with Kummer theory? – darij grinberg Feb 4 '10 at 10:21
I guess I was wrong. – Harry Gindi Feb 4 '10 at 15:50
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: 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|cite|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

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|cite|improve this answer

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|cite|improve this answer
Yes, it's part of a homework, but the factorization is already given at (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
@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

Your Answer


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.