$\sum_{1 \leq i,j \leq n, i|n, j|n} gcd(i,j)$

Question

$$S = \sum_{1 \leq i,j \leq n, i|n, j|n} gcd(i,j)$$

I can't find a way to solve this. Can I find a general formula or a way to solve this?

Answer 1

Let $n=p_1^{e_1}\cdots p_r^{e_r}$ be the prime factorization of the integer $n\geq 1$. The factorizations of the two divisors $i$ and $j$ of $n$ are $i=p_1^{k_1}\cdots p_r^{k_r}$ and $j=p_1^{l_1}\cdots p_r^{l_r}$, where $0\leq k_1,l_1\leq e_1$, $\ldots$, $0\leq k_r,l_r\leq e_r$. Your sum is then \begin{align*} S &~=~ \sum_{0\,\leq\, k_1,\,l_1\leq\, e_1,\,\,\ldots\,,\,\,0\,\leq\, k_r,\,l_r\leq\, e_r} p_1^{\min(k_1,\,l_1)}\cdots\, p_r^{min(k_r,\,l_r)} \\[1ex] &~=~\sum_{0\,\leq\, k_1,\,l_1\leq\, e_1}\!p_1^{\min(k_1,\,l_1)} ~\cdots\sum_{0\,\leq\, k_r,\,l_r\leq\, e_r}\!p_r^{min(k_r,\,l_r)}~~. \end{align*} It remains to calculate \begin{equation*} \sum_{0\,\leq\, k,\,l\,\leq\, e}p^{\min(k,\,l)} \,=\, \sum_{m=0}^e(2m+1)\,p^{e-m} \,=\, \frac{p^{\,e+2}+p^{\,e+1}-p\,(2e+3)+2\,e+1}{(p-1)^2}~~. \end{equation*} Write the rightmost expression above as $f(p,e)$. Then \begin{equation*} S = f(p_1,e_1)\cdots f(p_r,e_r)~. \end{equation*} Done.