# Help in proving a number theory problem

I have the following question from USAMO 2018:

For a given integer $$n\ge 2,$$ let $$\{a_1,a_2,…,a_m\}$$ be the set of positive integers less than $$n$$ that are relatively prime to $$n$$. Prove that if every prime that divides $$m$$ also divides $$n,$$ then $$a_1^k+a_2^k + \dots + a_m^k$$ is divisible by $$m$$ for every positive integer $$k$$.

I know that the value of $$m$$ is nothing but $$\phi(n)$$ where $$\phi$$ is the euler's totient function.

How do I proceed with this question?

My try:

I have decided to prove that when the required sum is computed modulo n, i get a multiple of $$\phi(n)$$ following which their given statement is proved.

I tried to divide the problem into two parts, one where k is even and the other when k is odd

I failed to deduce anything when k is odd. However when k is even, I can pair up those numbers which when raised to the required power have the same residue modulo n. However I am still not able to go ahead with it.

Any help please.

## 1 Answer

For each $$n\geq 1$$ let $$\begin{gather} A(n)=\{a:1\leq a\leq n\land\gcd(a,n)=1\}\\ S'_k(n)=\sum_{a\in A(n)}a^k \end{gather}$$ We have to prove that if each prime factor of $$\varphi (n)$$ divides $$n$$, then $$\varphi(n)\mid S'_k(n)$$. We argue by induction on $$k$$. Clearly, $$S'_0(n)=\varphi(n)$$ hence the assertion holds for $$k=0$$. Now given $$k>0$$, assume the assertion true for all $$j.

Lemma. Let $$p$$ be a prime divisor of $$n$$. If $$\varphi(p^en)\mid S'_k(p^en)$$, then $$\varphi(n)\mid S'_k(n)$$.

Proof. It's enough to consider $$e=1$$. First note that $$\varphi(pn)=p\varphi(n)$$ and $$A(pn)=\{a+hn:0\leq h\leq p-1\}$$ Consequenty \begin{align} S'_k(pn) &=\sum_{h=0}^{p-1}\sum_{a\in A(n)}(hn+a)^k\\ &=\sum_{h=0}^{p-1}\sum_{a\in A(n)}\sum_{j=0}^k\binom kj(hn)^{k-j}a^j\\ &=\sum_{h=0}^{p-1}\sum_{j=0}^k\binom kj(hn)^{k-j}S'_j(n)\\ &=pS'_k(n)+\sum_{h=0}^{p-1}\sum_{j=0}^{k-1}\binom kj(hn)^{k-j}S'_j(n)\\ &\equiv pS'_k(n)\pmod{\varphi(pn)} \end{align} from which the assertion follows. $$\square$$

Let \begin{align} &S_k(n)=\sum_{a=1}^n a^k& &F_k(n)=\frac{S_k(n)}{n^k}=\sum_{a=1}^n\left(\frac an\right)^k\\ &S'_k(n)=\sum_{a\in A(n)}a^k& &F'_k(n)=\frac{S'_k(n)}{n^k}=\sum_{a\in A(n)}\left(\frac an\right)^k\\ \end{align} Then $$F'_k=\mu\ast F_k$$, where $$\mu$$ is the Mobious function and $$\ast$$ is the Dirichlet convolution. Let $$N(n)=n$$ the identity function and $$S_k(n)=\sum_{i=1}^{k+1}c_{k,i}n^i$$ hence \begin{align} S'_k(n) &=n^k(\mu\ast F_k)(n)\\ &=n^k\sum_{i=1}^{k+1}c_{k,i}(\mu\ast N^{i-k})(n)\\ &=n^k\sum_{i=1}^{k+1}c_{k,i}(\mu\ast N^{i-k})(n) \end{align} But $$\mu\ast N=\varphi$$, $$\mu\ast N^0=I$$, where $$I(1)=1$$ and $$I(n)=0$$ for $$n>1$$, and for $$i we have the Jordan's totient function \begin{align} (\mu\ast N^{i-k})(n) &=n^{i-k}\prod_{p\mid n}(1-p^{k-i})\\ &=n^{i-k}\prod_{p\mid n}\frac{1-p^{k-i}}{1-p}\prod_{p\mid n}\frac{1-p}p\prod_{p\mid n}p\\ &=\pm n^{i-k}Q_{k-i}(n)\frac{\varphi(n)}nR(n)\\ &=\pm n^{i-k-1}Q_{k-i}(n)\varphi(n)R(n) \end{align} where \begin{align} &Q_j(n)=\prod_{p\mid n}\frac{1-p^j}{1-p}& &R(n)=\prod_{p\mid n}p \end{align} Hence we get for $$n>1$$ \begin{align} S'_k(n)=c_{k,k+1}n^k\varphi(n)\pm\sum_{i=1}^{k-1}c_{k,i}n^{i-1}Q_{k-i}(n)\varphi(n)R(n) \end{align}

Now let $$p$$ be a prime divisor of $$\varphi(n)$$ and let $$\nu_p$$ denote the $$p$$-adic valuation. By assumption $$p\mid n$$. By Faulhaber's Formula we have $$c_{k,k+1}=\frac 1{k+1}$$ and $$c_{k,1}=B_k$$ the Bernoulli number. Cearly, $$\nu_p(c_{k,k+1}n^k)\geq 0$$. On the other hand $$c_{k,1}=B_k=0$$ for odd $$k$$, while for even $$k$$ by von Staudt-Clausen Theorem, the denominator of $$c_{k,1}=B_k$$ is given by $$\prod_{p-1\mid k}p$$ which is square-free. Consequently, $$\nu_p(c_{k,k+1}n^k)\geq 0$$ and $$\nu_p(c_{k,1}R(n))\geq 0$$.

Let $$e\geq 1$$ such that $$\nu_p(c_{k,i}p^en)\geq 0$$ for $$1. Then $$\varphi(p^en)\mid S'_k(p^en)$$. By Lemma, we get $$\varphi(n)\mid S'_k(n)$$.