∑gcd(N, i)の計算

$$\sum _{i=1}^{n}gcd(n,i)を求めたい。$$

さっそくやり方。
$$\begin{gathered} \sum _{i=1}^{n}gcd(n,i) \\ =\sum _{d|n}d\times (gcd(n,i)=dとなるようなi(1\le i\le n)の個数) \\ =\sum _{d|n}d\times (gcd(n/d,i)=1となるようなi(1\le i\le n/d)の個数) \\ =\sum _{d|n}d\times \phi (n/d)(\phi はオイラー関数) \\ =\sum _{d|n}n/d\times \phi (d) \\ (ここで、n=\prod _{i=1}^k{p}_i^{e_i},d=\prod _{i=1}^k{p}_i^{f_i}とすると) \\ =\sum _{d|n}(\prod _{i=1}^k{p}_i^{e_i-f_i})\times (\prod _{i=1}^k(p_i^{f_i+1}-p_i^{f_i})/p_i)(ただし、fi=0のときのみ例外となることに注意) \\ =\prod _{i=1}^k((\sum _{j=1}^{e_i}(p_i^{e_i+1}-p_i^{e_i})/p_i)+1) \\ =n\prod _{i=1}^k((p_i-1)(e_i+1)+1)/p_i) \\ よって、nの素因数分解により\sum _{i=1}^{n}gcd(n,i)が求まる。 \end{gathered}$$
おかしいところあったら指摘してもらえると助かります。