Let n, k be positive integers. Prove that \(\sum_{i=1}^n k^{\gcd(i,n)}\) is divisible by n.

**GD Star Rating**

*loading...*

Let n, k be positive integers. Prove that \(\sum_{i=1}^n k^{\gcd(i,n)}\) is divisible by n.

Evaluate the following sum

\(\displaystyle\sum_{m=1}^\infty \sum_{\substack{n\ge 1\\ (m,n)=1}} \frac{x^{m-1}y^{n-1}}{1-x^m y^n}\)

when |x|, |y|<1.

(We write (m,n) to denote the g.c.d of m and n.)

The best solution was submitted by Hojin Kim (김호진, 2009학번). Congratulations!

Here is his Solution of Problem 2010-3.

Alternative solutions were submitted by 정성구 (수리과학과 2007학번, +3), 임재원 (2009학번, +3), Prach Siriviriyakul (2009학번, +3), 서기원 (2009학번, +3), 김치헌 (수리과학과 2006학번, +2).

The problem had a slight problem when xy=0; It is necessary to assume 0^{0}=1.