6
$\begingroup$

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

  • 0
    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$.2013-01-25

2 Answers 2

1

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.

  • 0
    Caveat: This argument works only for $a \geq 0$. It needs to be modified to work for negative $a$.2015-03-15
1

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$