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.
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<k$.
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<k$ 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<i<k$. Then $\varphi(p^en)\mid S'_k(p^en)$. By Lemma, we get $\varphi(n)\mid S'_k(n)$.