most recent 30 from http://mathoverflow.net 2013-05-20T13:46:30Z http://mathoverflow.net/feeds/question/14062 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/14062/how-to-factorize-xn-1-in-z-pz Alexandru Moșoi 2010-02-03T22:05:34Z 2010-02-28T08:53:34Z

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

http://mathoverflow.net/questions/14062/how-to-factorize-xn-1-in-z-pz/14067#14067 Qiaochu Yuan 2010-02-03T22:22:31Z 2010-02-03T22:22:31Z

<p>I describe how to do this generally in my answer to <a href="http://mathoverflow.net/questions/10457/what-are-the-prime-ideals-in-rings-of-cyclotomic-integers" rel="nofollow">question #16457</a> 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$.</p>

http://mathoverflow.net/questions/14062/how-to-factorize-xn-1-in-z-pz/14068#14068 darij grinberg 2010-02-03T22:23:42Z 2010-02-03T22:23:42Z

<p>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).</p> <p>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?</p>

http://mathoverflow.net/questions/14062/how-to-factorize-xn-1-in-z-pz/14156#14156 Kevin O'Bryant 2010-02-04T15:08:17Z 2010-02-04T15:08:17Z

<p>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: <a href="http://www.wolframalpha.com/" rel="nofollow">http://www.wolframalpha.com/</a> 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).$$</p> <p>Annoying to have "2" instead of "-1" in GF(3), but that's the price of having a machine do your work for you.</p>