Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 5 down vote favorite
1

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}.$$

share|improve this question
What have you tried? – Qiaochu Yuan Oct 20 '12 at 1:49
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 at 6:58

1 Answer

up vote 1 down vote

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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