What is the number of irreducible factors of $x^{255}-1$ over $\mathbb{Q}$ and $\mathbb{F}_2$?

Question

What is the number of irreducible factors of $x^{255}-1$ over $\mathbb{Q}$ and $\mathbb{F}_2$?

Over $\mathbb{Q}$, $x^{255}-1$ factorizes as $(x-1) \Phi_{5} \Phi_{51}\Phi_{255}$ with all of them irreducible, but I am not sure if this is correct. As for $\mathbb{F}_2$ I have no clue about how to proceed.

Answer 1

Welcome to MSE! Hint: The polynomial $x^{p^n}-x$ in ${\Bbb Z}_p[x]$, $p$ prime, is the product of all monic irreducible polynomials in ${\Bbb Z}_p[x]$ whose degree is a divisor of $n$, i.e., $$\sum_{d|n} d N_d = p^n,$$ where $N_d$ is the number of monic irreducible polynomials of degree $d$ in ${\Bbb Z}_p$.

To be more than a comment, here is the factorization for $x^{16}-x$ in ${\Bbb Z}_2[x]$, which is part of the problem:

Degree 4: $x^4+x+1$, $x^4+x^3+1$ (conjugate to the first polynomial, the zeros of these polynomials are primitive), and $x^4+x^3+x^2+x+1$ (the zeros are 5-th roots of unity).

Degree 2: $x^2+x+1$.

Degree 1: $x$ and $x+1$.

Now to the solution: $$256 = 30\cdot 8 + 3\cdot 4 + 1\cdot 2 + 2\cdot 1.$$

Answer 2

Your factorization over $\Bbb{Q}$ is not quite correct; note that $255=3\times5\times17$.

For a factorization over $\Bbb{F}_2$; use the fact that $x^{p^n}=x$ for all $x\in\Bbb{F}_{p^n}$. This means $x^{255}=1$ for all nonzero $x\in\Bbb{F}_{2^8}$, and so $x^{255}-1$ is divisible by the minimal polynomial of every element of $\Bbb{F}_{2^8}^{\times}$. So every irreducible polynomials whose degree divides $8$ is a factor of $x^{255}-1$.

Answer 3

Over $\Bbb Q$, $x^n-1$ factors as $\prod_{d\mid n}\Phi_d(x)$ where the $\Phi_d$ are cyclotomic polynomials. These are irreducible over $\Bbb Q$. The number of irreducible factors of $x^n-1$ over $\Bbb Q$ is the number of (positive integer) divisors of $n$.

Answer 4

This is an answer which tries to list explicitly the factors, aided by computer support, here sage. "Human" comments show why it is so.

• First of all, let us get the factors over $\Bbb Q$. It is clear that $$X^{255}-1 =\prod_{d\in\{1, 3, 5, 15, 17, 51, 85, 255\}}\Phi_d(X) \ , $$ and the factors on the R.H.S above are the cyclotomic polynomials $\Phi_d$ of degree $d$, where $d$ runs in the list of all (positive) divisors of $255$, as listed above.

Let us check this in sage, and also print some first factors:

sage: R.<X> = PolynomialRing(QQ)
sage: 255.divisors()
[1, 3, 5, 15, 17, 51, 85, 255]
sage: prod( [ cyclotomic_polynomial(d, X) for d in 255.divisors() ] ) == X^255 - 1 
True
sage: cyclotomic_polynomial(1, X )
X - 1
sage: cyclotomic_polynomial( 3, X )
X^2 + X + 1
sage: cyclotomic_polynomial( 5, X )
X^4 + X^3 + X^2 + X + 1
sage: cyclotomic_polynomial( 15, X )
X^8 - X^7 + X^5 - X^4 + X^3 - X + 1

(The next cyclotomic polynomial, $\Phi_{17}(X)$ is the sum $1+X+\dots+X^{16}$. The further polynomials have too many terms for the place available here.)

• Now let us work in characteristic $2$. Consider the field $$\Bbb F_{256}=\Bbb F_{2^8}$$ with $256=2^8$ elements. The corresponding Frobenius morphism $x\to x^{256}$ fixes every element. It fixes $0$, of course, and for all $x\ne 0$ we have $0=x^{256}-x=x(x^{255}-1)$, so the last factor vanishes. Every element $x$ in $\Bbb F_{256}^ \times$ generates a subfield $\Bbb F_2(x)$, which has degree $2^r$, $r=1,2,4,8$ being a divisor of $8$, its minimal polynomial is thus an irreducible polynomial of this degree $r$. Conversely, each irreducible polynomial of degree $r=1,2,4,8$ has a splitting field isomorphic to a subfield of $\Bbb F_{255}$. So we expect a decomposition of the shape: $$ X^{255}-1 = \prod'_{P\text{ irreducible of degree }r=1,2,4,8}P(X)\ , $$ where the prime means we are omitting the one irreducible polynomial $X$.

Using sage, we can get all those factors:

sage: R.<X> = PolynomialRing( GF(2) )
sage: R
Univariate Polynomial Ring in X over Finite Field of size 2 (using GF2X)
sage: for fctr, multiplicity in (X^255-1).factor():
....:     print "&", latex(fctr), '\\\\'
....:  

The generated code was pasted in the following aligned block: $$ {\tiny \begin{aligned} & X + 1 \\ & X^{2} + X + 1 \\ & X^{4} + X + 1 \\ & X^{4} + X^{3} + 1 \\ & X^{4} + X^{3} + X^{2} + X + 1 \\ & X^{8} + X^{4} + X^{3} + X + 1 \\ & X^{8} + X^{4} + X^{3} + X^{2} + 1 \\ & X^{8} + X^{5} + X^{3} + X + 1 \\ & X^{8} + X^{5} + X^{3} + X^{2} + 1 \\ & X^{8} + X^{5} + X^{4} + X^{3} + 1 \\ & X^{8} + X^{5} + X^{4} + X^{3} + X^{2} + X + 1 \\ & X^{8} + X^{6} + X^{3} + X^{2} + 1 \\ & X^{8} + X^{6} + X^{4} + X^{3} + X^{2} + X + 1 \\ & X^{8} + X^{6} + X^{5} + X + 1 \\ & X^{8} + X^{6} + X^{5} + X^{2} + 1 \\ & X^{8} + X^{6} + X^{5} + X^{3} + 1 \\ & X^{8} + X^{6} + X^{5} + X^{4} + 1 \\ & X^{8} + X^{6} + X^{5} + X^{4} + X^{2} + X + 1 \\ & X^{8} + X^{6} + X^{5} + X^{4} + X^{3} + X + 1 \\ & X^{8} + X^{7} + X^{2} + X + 1 \\ & X^{8} + X^{7} + X^{3} + X + 1 \\ & X^{8} + X^{7} + X^{3} + X^{2} + 1 \\ & X^{8} + X^{7} + X^{4} + X^{3} + X^{2} + X + 1 \\ & X^{8} + X^{7} + X^{5} + X + 1 \\ & X^{8} + X^{7} + X^{5} + X^{3} + 1 \\ & X^{8} + X^{7} + X^{5} + X^{4} + 1 \\ & X^{8} + X^{7} + X^{5} + X^{4} + X^{3} + X^{2} + 1 \\ & X^{8} + X^{7} + X^{6} + X + 1 \\ & X^{8} + X^{7} + X^{6} + X^{3} + X^{2} + X + 1 \\ & X^{8} + X^{7} + X^{6} + X^{4} + X^{2} + X + 1 \\ & X^{8} + X^{7} + X^{6} + X^{4} + X^{3} + X^{2} + 1 \\ & X^{8} + X^{7} + X^{6} + X^{5} + X^{2} + X + 1 \\ & X^{8} + X^{7} + X^{6} + X^{5} + X^{4} + X + 1 \\ & X^{8} + X^{7} + X^{6} + X^{5} + X^{4} + X^{2} + 1 \\ & X^{8} + X^{7} + X^{6} + X^{5} + X^{4} + X^{3} + 1 \end{aligned}} $$