2
$\begingroup$

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

$\endgroup$
7
  • 4
  • 1
    $\begingroup$ 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. $\endgroup$
    – user2734
    Feb 3, 2010 at 23:17
  • 1
    $\begingroup$ Abstract Algebra by Dummit and Foote has a section on finite fields (14.3) which should have all the info you need. $\endgroup$ Feb 3, 2010 at 23:34
  • 3
    $\begingroup$ What the heck does this have to do with Kummer theory? $\endgroup$ Feb 4, 2010 at 10:21
  • 3
    $\begingroup$ I guess I was wrong. $\endgroup$ Feb 4, 2010 at 15:50

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I tried countless variations on wolframalpha, but not "factor x^26-1". thank you $\endgroup$ Feb 10, 2010 at 23:49
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Feb 3, 2010 at 22:34
  • 1
    $\begingroup$ @Alexandru: You are right, there is a typo, and the last factor should be $X^3+X^2-X+1$. $\endgroup$ Feb 3, 2010 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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