# How to factorize X^n - 1 in Z/pZ?

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

-
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

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.

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

-

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?

-
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
@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