Compute $\sum_{i=1}^n\frac i{\gcd(i,n)}$

Question

Compute $$\sum_{i=1}^n\frac i{\gcd(i,n)}$$

The actual problem description is as follows : $$\sum_{i=1}^{15}\frac i{\gcd(i,{15})}$$

But I'd like a formula which could be used for large $n$.

Answer 1

We have that $$\begin{align*} \sum_{i=1}^n\frac{i}{\gcd(n,i)}&=1+\frac{1}{2}\left(\sum_{i=1}^{n-1}\frac{i}{\gcd(n,i)}+\sum_{i=1}^{n-1}\frac{i}{\gcd(n,n-i)}\right)\\ &=1+\frac{1}{2}\left(\sum_{i=1}^{n-1}\frac{i}{\gcd(n,i)}+\sum_{i=1}^{n-1}\frac{n-i}{\gcd(n,i)}\right)\\ &=1+\frac{1}{2}\sum_{i=1}^{n-1}\frac{n}{\gcd(n,i)} =\frac{1}{2}+\frac{1}{2}\sum_{i=1}^{n}\frac{n}{\gcd(n,i)}\\ &=\frac{1}{2}+\frac{1}{2}\sum_{d|n}\frac{n}{d}\left|\{i\in[1,n]: \gcd(i,n)=d\}\right|\\ &=\frac{1}{2}+\frac{1}{2}\sum_{d|n}\frac{n}{d}\left|\{k\in[1,n/d]: \gcd(k,n/d)=1\}\right|\\ &=\frac{1}{2}+\frac{1}{2}\sum_{d|n}\frac{n}{d}\varphi(n/d) =\frac{1}{2}\left(1+\sum_{d|n}d\varphi(d)\right). \end{align*}$$ Since $n\to\sum_{d| n}d\varphi(d)$ is multiplicative and for any prime $p$, $$\sum_{d|p^r}d\varphi(d)=1+\sum_{k=1}^r p^k\varphi(p^k)=1+\sum_{k=1}^r (p^{2k}-p^{2k-1})=\frac{p^{2r+1}+1}{p+1},$$ it follows that $$f(n):=\sum_{i=1}^n\frac{i}{\gcd(n,i)}=\frac{1}{2}\left(1+\prod_{j=1}^m\frac{p_j^{2r_j+1}+1}{p_j+1}\right).$$ where $n=\prod_{j=1}^m p_j^{r_j}$ is the prime factorization of $n$. For example: $$\begin{align*} f(15)&=f(3\cdot 5)=\frac{1}{2}\left(1+\frac{3^3+1}{3+1}\cdot \frac{5^3+1}{5+1}\right)=74,\\ f(500)&=f(2^2\cdot 5^3)=\frac{1}{2}\left(1+\frac{2^5+1}{2+1}\cdot \frac{5^7+1}{5+1}\right)=71616. \end{align*}$$ More details and references for this sum can be found in OEIS: A057661 (see lulu's comment).