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