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

**GD Star Rating**

*a WordPress rating system*

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

Let 1≤a_{1}<a_{2}<…<a_{k}<n be a sequence of integers such that gcd(a_{i},a_{j})=1 for all 1≤i<j≤k. What is the maximum value of k?

(Problem updated on Sep. 26, 8AM: gcd(a_{i},a_{j})=1.)