Find the value of this series:

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


closed as off-topic by TravisJ, user147263, Ofir Schnabel, SchrodingersCat, user26857 Nov 9 '15 at 15:38

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – TravisJ, Ofir Schnabel, SchrodingersCat, user26857
If this question can be reworded to fit the rules in the help center, please edit the question.


For each divisor $d$ of $n$ there are exactly $\phi\left(\frac nd\right)$ terms in the sum whose value is $\frac nd$, so

$$\sum_{j=1}^n\frac n{(j,n)}=\sum_{d\mid n}\frac nd\phi\left(\frac nd\right)=\sum_{d\mid n}d\phi(d)=\sum_{d\mid n}\phi(d^2)$$

  • $\begingroup$ Could you explain (or provide some reference) why there are exactly $\phi(n/d)$ terms in the sum with value $n/d$? $\endgroup$ – A.P. Nov 10 '15 at 16:07
  • $\begingroup$ I think I got it. If the term for $1 \leq i \leq n$ has value $n/d$, then $\gcd(i, n) = d$. On the other hand, this happens iff $\gcd(i, n/d) = n/d$. Is this correct? $\endgroup$ – A.P. Nov 10 '15 at 16:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.