Number of irreducible factors of $x^{p^n + 1} - 1$ over $\Bbb F_p$ Let $p,n$ be two odd prime numbers. I want to show that the number of irreducible factors of $x^{p^n + 1} - 1$ over $\Bbb F_p$ is
$$N = \frac{p^n-p}{2n} + \frac{p-1}{2} + 2$$
I know that this is equal to $\sum_{d\mid (p^n+1)}\frac{\phi(d)}{\operatorname{ord}_d(p)}$ (see How many irreducible factors does $x^n-1$ have over finite field?). I checked the equality with SAGE for some pairs $(p,n)$. But how would I prove the above equality?
Thank you!
 A: The number of irreducible factors of $X^m-1$ for $p\nmid m$, is the number of cycles
of the Frobenius map $F:\alpha\to\alpha^p$ in its action
on $\mu_m$, the set of $m$-th roots
of unity in an algebraic closure of $\Bbb F_p$. This is the same as the number of orbits
of $\phi:a\mapsto pa$ on $\Bbb Z/m\Bbb Z$.
In our case $m=p^n+1$. Then $\phi^n(a)=-a$ and so $\phi^{2n}(a)=a$.
Every orbit of $\phi$ on $\Bbb Z/m\Bbb Z$ has length dividing $2n$.
For $k\mid 2n$, the number of solutions to $\phi^k(a)=a$
is the number of solutions to the congruence $(p^k-1)a\equiv0\pmod{p^n+1}$
and equals $a_k=\gcd(p^k-1,p^n+1)$.
Now $a_1=\gcd(p-1,p^n+1)=\gcd(p-1,p+1)=2$. Also
$a_2=\gcd(p^2-1,p^n+1)=\gcd(p^2-1,p+1)=p+1$ as $p^n\equiv p\pmod{p^2}$.
Finally $a_n=\gcd(p^n-1,p^n+1)=\gcd(p^n-1,2)=2$.
The orbits of length $1$ comprise two elements, those of length $2$
comprise $(p+1)-2 = p-1$ elements and there are no orbits of length $n$.
Therefore the orbits of length $2n$ comprise
$$p^n+1-2-(p-1)=p^n-p$$
elements and so there are $2$ orbits of length $1$, $(p-1)/2$ of length
$2$ and
$$\frac{p^n-p}{2n}$$
of length $2n$. The number of irreducible factors is the total number
of orbits, namely
$$\frac{p^n-p}{2n}+\frac{p-1}2+2.$$
