Project Euler Problem 797
A monic polynomial is a single-variable polynomial in which the coefficient of highest degree is equal to 1.
Solution
Answer: 47722272
Let
$$A(n)=\Phi_n(2),$$
where $\Phi_n(x)$ is the $n$-th cyclotomic polynomial.
Every monic divisor of $x^n-1$ is obtained by choosing a subset of the cyclotomic factors
$$x^n-1=\prod_{d\mid n}\Phi_d(x).$$
Hence, evaluating at $x=2$, the sum of all divisors of $x^n-1$ is
$$G(n)=\prod_{d\mid n}(1+A(d)).$$
The quantity $P_n(2)$ counts only those divisors whose minimal cyclogenic order is exactly $n$, so Möbius inversion gives
$$P_n(2)=\sum_{d\mid n}\mu!\left(\frac nd\right)G(d).$$
Therefore
$$Q_N(2)=\sum_{n\le N}P_n(2).$$
Using the standard identity
$$A(n)=\prod_{d\mid n}(2^d-1)^{\mu(n/d)},$$
one can sieve all values up to $10^7$, compute $G(n)$, then apply Möbius inversion and accumulate the total modulo $1,000,000,007$.
The computation reproduces the check value
$$Q_{10}(2)=5598,$$
and for $N=10^7$ yields:
Answer: 116172640