# How many irreducible factors does $x^n-1$ have over finite field?

The polynomial $x^n-1$ is needed to be factorized into irreducibles over finite field $\mathrm{F}_q$. How many are them?

I guess the question is about of number of cyclotomic cosets. Let $p$ be the smallest positive that $n$ divides $q^p - 1$. The desired factors are the minimal polynomials of elements from field $\mathrm{F}_{q^p}$. Each minimal polynomial is known to have roots those can be obtained with help of some $q$-cyclomatic coset of $\{0, 1, \ldots, n-1\}$. So, given $n$, $q$, $p$, how many unique $q$-cyclotomic cosets of $\{0, 1, \ldots, n-1\}$ exist?

• Looks like you are assuming that $\gcd(n,q)=1$ for otherwise $x^n-1$ has repeated factors (and no $p$ of the required type exists). I'm afraid I'm not aware of any nice formula for the number of cyclotomic cosets in your relatively general setting. The problem is complicated by the fact that not all cyclotomic cosets have the same size. The primitive $n$th roots of unity do fall into full size cyclotomic cosets of size $p$. But the size of non-primitive cyclotomic cosets depends on the order of $q$ modulo a proper factor of $n$, and that may (or may not) be a proper factor of $p$. Commented Oct 22, 2013 at 18:40
• Commented Dec 26, 2016 at 12:50

Typing up something that illustrates the difficulty of giving a precise answer in terms of just the given data.

I am assuming that $$\gcd(n,q)=1$$ for if $$n$$ is divisible by the characteristic, call it $$\ell$$, then $$x^n-1=(x^{n/\ell}-1)^\ell$$, and we are reduced to study $$x^{n/\ell}-1$$ instead.

Then the roots of $$x^n-1$$ are the $$n$$th roots of unity. If $$\zeta$$ is one of them, then its order is $$d\mid n$$. The degree of the minimal polynomial of $$\zeta$$ equals the order of the (coset of) $$q$$ in the group $$\Bbb{Z}_d^*$$, and as $$d$$ may be a proper factor of $$n$$, this order, call it $$\operatorname{ord}_d(q)$$ may be a proper factor of $$p$$ (it is trivially always a factor). The number of roots of order $$d$$ is given by the Euler totient function $$\phi(d)$$.

This gives us the following formula for the irreducible factors of $$x^n-1$$: $$\sum_{d\mid n}\frac{\phi(d)}{\operatorname{ord}_d(q)}.$$ I don't know how to simplify this.

As an example let's look at the case $$q=2, n=15$$. The factors of $$15$$ are $$1,3,5,15$$ while the respective orders $$\operatorname{ord}_d(2)$$ are $$1,2,4,4$$. Thus the number of irreducible factors of $$x^{15}-1$$ is $$\frac11+\frac22+\frac44+\frac84=5.~~~~~$$ The degrees of the factors are the sizes of the cyclotomic cosets (undoubtedly you knew this). In this case they are $$1$$ (first root of unity), $$2$$ (third roots of unity), $$4$$ (fifth) and two more factors of degree $$4$$ accounting for the eight primitive roots of unity. As I "promised" we observe that $$\operatorname{ord}_5(2)=4$$ $$=\operatorname{ord}_{15}(2)$$, but $$\operatorname{ord}_3(2)=4<\operatorname{ord}_{15}(2)$$. This, of course, reflects the fact that the third roots of unity belong to a smaller extension field than the fifth roots of unity.

• Great answer! To clarify, $\frac{\varphi(d)}{ord_d(q)}$ is the number of irreducible factors of degree $d$, right?
– qinr
Commented May 7, 2019 at 4:06
• Correct, @qinr. Commented May 7, 2019 at 4:12