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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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