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?
 A: 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.
