Number of Irreducible Factors of $x^{63} - 1$ I have to find the number of irreducible factors of $x^{63}-1$ over $\mathbb F_2$ using the $2$-cyclotomic cosets modulo $63$.
Is there a way to see how many the cyclotomic cosets are and what is their cardinality which is faster than the direct computation?
Thank you.
 A: Direct computation is pretty fast in this case.
The poly. $x^{63} -1 $ factors as cyclotomic polys $\Phi_d$ for $d \mid 63$, so
$d = 1, 3, 9, 7, 21, 63.$
The corresponding degrees of $\Phi_d$ are $\phi(d)$:  $1, 2, 6, 6, 12, 36$.
To compute how $\Phi_d$ factors over $\mathbb F_2$, you have to compute
the subgroup of $(\mathbb Z/d)^{\times}$ generated by $2$; its index is
the number of factors.  
Since all the $d$ divide $63$, and $2^6 = 64 \equiv 1 \bmod 63$, these groups, 
and the corresponding indices,
are pretty fast to compute.
Ultimately, one finds $13$ factors (as was already recorded in ALGEAN's answer).
A: Note that $x^{p^n}-x\in\mathbb{Z}_p[x]$ equals to product of all irreducible factors of degree $d$ such that $d|n$. Suppose $w_p(d)$ is the number of irreducible factors of degree $d$ on $\mathbb{Z}_p$, then we have 
$$p^n=\sum_{d|n}dw_p(d)$$
now use Mobius Inversion Formula to obtain
$$w_p(n)=\frac1{n}\sum_{d|n}\mu(\frac{n}{d})p^d.$$
use above identity to obtain
$$w_p(1)=p$$
$$w_p(q)=\frac{p^q-p}{q}$$
$$w_p(rs)=\frac{p^{rs}-p^r-p^s+p}{rs}$$
where $q$ is a prime number and $r,s$ distinct prime numbers. 
Now you need to calculate $w_2(1)+w_2(2)+w_2(3)+w_2(6)\color{#ff0000}{-{1}}$. By using above formulas you can see that the final answer is $13$. 
