Burnside's Lemma Deduce That:


$$\sum\_{i=1}^{n} a^{\gcd(i,n)} $$


is divisible by $n$


it's a beautiful result. but i want to prove it without any abstract algebraic tools such as Burnside's Lemma...


is there any simple Number-Theoretic proof for it?



Simple proof for $\sum_{i=1}^n a^{\gcd(i,n)} $ is divisible by $n$
Our sum equals $$S\_n(a):=\sum\_{d|n} \varphi\left(\frac{n}d\right)a^d.$$
Fix a prime power $p^k$ which divides $n$ (but $p^{k+1}$ does not divide $n$, we write this as $\nu\_p(n)=k$), we have to prove that $p^k$ divides $S\_n(a)$. If $p$ divides $a$, then $p^k$ divides each summand. Indeed, $\nu\_p(\varphi(n/d))\geqslant \nu\_p(n/d)-1=\nu\_p(n)-\nu\_p(d)-1\geqslant \nu\_p(n)-d$ since $d<p^d$), thus $\nu\_p(\varphi(n/d)a^d)\geqslant \nu\_p(n)$ as desired. 


Now consider the remaining case: $p$ does not divide $a$. Fix a divisor $s$ of $n$ such that $p$ does not divide $s$ and consider the set of divisors $\{s,ps,p^2s,\dots,p^ks\}$. I claim that $p^k$ divides the sum of $\varphi\left(\frac{n}d\right)a^d$ over $d$ in each such a group. The claim follows. For proving this denote $\varphi(n/p^ks)=A$, then we have $\varphi(n/p^{k-i}s)=p^{i-1}(p-1)A$ for $i=1,\dots,k$. So, it suffices to prove that (if we denote $b=a^s$) $p^k$ divides
$$
b^{p^k}+(p-1)(b^{p^{k-1}}+pb^{p^{k-2}}+\dots+p^{k-1}b)=p^kb+\sum\_{i=0}^{k-1} p^i\left(b^{p^{k-i}}-b^{p^{k-i-1}}\right),
$$
$p^k$ divides each summand by Euler theorem: $b^{p^m}-b^{p^{m-1}}=b^{p^{m-1}}(b^{\varphi(p^m)}-1)$ is divisible by $p^m$


