# Seeking a proof of $\sum_{d|n}\phi(\frac{n}{d})a^d\equiv 0 \mod{n}$, where $\phi$ is the Euler Totient Function.

I need to prove the proposition.

Let $a$ be an arbitrary integer. Then for every positive integer $n$, we have $$\sum_{d \mid n}\phi\left(\frac{n}{d}\right)a^d\equiv0\pmod{n}.$$

-
I used the Burnside's Lemma (Cauchy-Frobenius), this is Group and rings Theory applied, but I want to know if I can use just number theory, anyone tolds me that I can find a solution to this problem using "Pólya counting" But I don't understand it – Elmo goya Oct 20 '12 at 1:57
You shouldn't think of mathematical subjects as being divided like that. Burnside's lemma is Burnside's lemma. You could call it group theory. It would be equally valid to call it combinatorics. This particular application could safely be called number theory. The labels don't matter. Polya enumeration is a special case of Burnside's lemma. – Qiaochu Yuan Oct 20 '12 at 2:00
I posted just now, but didn't see the two comments that appeared very recently. I hope my post is useful in spite of the overlap with these comments. – Marko Riedel Oct 20 '12 at 2:18
Check it directly when $n$ is a prime power. For other $n$, pick a prime factor $p$ of $n$ and write $n$ as a product of a $p$-power and another number relatively prime to $p$. Divisors of $n$ break up in a similar way to this, and $\varphi$ is multiplicative, so you should be able to derive the result by induction on the number of different prime factors of $n$. – KCd Jan 25 '13 at 6:58

I suspect the poster is asking for an elementary solution, which this isn't. Anyway.

The cycle index of the cyclic group on $n$ elements is $$Z(C_n) = \frac{1}{n} \sum_{d|n} \phi(n/d) x_{n/d}^d$$ where the $x_d$ are the variables.

Hence, by the Polya Enumeration Theorem, the quantity $$Z(C_n)_{x_1 = a, x_2 = a, x_3 = a, \ldots}$$ counts the number of distinct necklaces on $n$ elements under rotation where the slots on the necklace hold one of $a$ colors.

Hence, combinatorially, the following quantity must be an integer $$\frac{1}{n} \sum_{d|n} \phi(n/d) a^d$$ because it counts the number of necklaces.

There is more at Wikipedia.

-
The OP has indicated that he already knows the solution using Burnside's lemma, and PET is a special case of this. – Qiaochu Yuan Oct 20 '12 at 2:19
Ty, but... The answer I need is without the $\frac{1}{n}$, I think that the answer comes near – Elmo goya Oct 20 '12 at 2:24
Caveat: This argument works only for $a \geq 0$. It needs to be modified to work for negative $a$. – darij grinberg Mar 15 '15 at 0:36

Let $p$ be a prime divisor of $n$. Let $\frac{n}{p^{v_p(n)}}=m$.

Now by partitioning the divisors by the $p$-adic order, we have $$\sum_{d|n} \phi (\frac{n}{d})a^d = \sum_{x|n,(x,p)=1} \sum_{i=0}^{v_p(n)} \phi (\frac{n}{xp^i}) \cdot a^{xp^i}= \sum_{x|m} \sum_{i=0}^{v_p(n)} \phi (p^{v_p(n)-i} \cdot \frac{m}{x}) \cdot a^{xp^i}=$$ $$\sum_{x|m} \sum_{i=0}^{v_p(n)} \phi (p^{v_p(n)-i} ) \cdot \phi (\frac{m}{x})a^{xp^i} = \sum_{x|m} \phi (\frac{m}{x}) \sum_{i=0}^{v_p(n)} \phi(p^{v_p(n)-i})a^{xp^i}$$

It suffices to show that (by replacing $a^x$ by $a$ and $v_p(n)$ with $n$) for all $n$ we have $$\sum_{i=0}^{n} \phi(p^{n-i})a^{p^i} \equiv 0 \pmod{p^{n}}$$

After proving this, we can use this for all primes and we will be done.

We proceed with induction. For $n=1$, we have $\phi(p) a + \phi(1) a^p \equiv (p-1)a+ a \equiv 0 \pmod{p}$.

Assume that this is true for $k-1$. We show that this is true for $k$ as well.

We have $$a^{p^k} + (p-1)a^{p^{k-1}} + p(p-1) a^{p^{k-2}} + \cdots$$ $$= a^{p^k} + (p-1)a^{p^{k-1}} + p((p-1)a^{p^{k-2}} + p(p-1)a^{p^{k-3}} + \cdots )$$ $$=a^{p^k} + (p-1)a^{p^{k-1}} + p(\text{something divisible by } p^{k-1} - a^{p^{k-1}}) \text{ (by induction hypothesis)}$$ $$=a^{p^k}-a^{p^{k-1}} + \text{something divisible by } p^k \equiv 0 \pmod{p^k}$$ as desired. We are done. $\blacksquare$

-