Problem: Let $n \ge 2$ be an integer, and let $\{a_1, \dots, a_m\}$ denote
the $m = \varphi(n)$ integers less than $n$ and relatively prime to $n$.
Assume that every prime divisor of $m$ also divides $n$.
Prove that $m$ divides $a_1^k + \dots + a_m^k$ for every positive
integer $k$.

Solution: For brevity, given any $n$, we let $A(n) = \left\{ 1 \le x \le n, \gcd(x,n) = 1 \right\}$
(thus $|A(n)| = \varphi(n)$).
Also, let $S(n,k) = \sum_{a \in A(n)} a^k$.

We will prove the stronger statement (which eliminates the hypothesis on $n$).
\begin{claim*}
  Let $n \ge 2$ be arbitrary (and $k \ge 0$).
  If $p \mid n$, then \[ \nu_p (\varphi(n)) \le \nu_p(S(n,k)). \]
\end{claim*}

We start with the special case where $n$ is a prime power.
\begin{lemma*}
  Let $p$ be prime, $e \ge 1$, $k \ge 0$.
  We always have
  \[ S(p^e, k) = \sum_{x \in A(p^e)} x^k \equiv 0 \pmod{p^{e-1}}.  \]
\end{lemma*}
\begin{proof}
  For $p$ odd, this follows by taking a primitive root $g$ modulo $p^{e}$.
  We will have
  \[ S(p^e, k) \equiv 1 + g^k + g^{2k} + \dots + g^{(\varphi(p^e)-1)k}
    \equiv \frac{g^{\varphi(p^e) k} - 1}{g^k - 1}. \]
  If $p-1 \nmid k$, then the denominator is not divisible by $p$
  and hence the entire expression is $0 \pmod{p^e}$.
  In the other case where $p-1 \mid k$, since $\nu_p(\varphi(p^e)) = e-1$,
  the exponent lifting lemma implies
  \[ \nu_p\left( (g^k)^{\varphi(p^e)} - 1 \right) = \nu_p(g^k-1) + (e-1) \]
  and so the conclusion is true here too.

  In the annoying case $p = 2$, the proof is broken into two cases:
  for $k$ odd it follows by pairing $x$ with $2^e-x$
  and when $k$ is even one can take $5$ as a generator
  of all the quadratic residues as in the $p > 2$ case.
\end{proof}
\begin{corollary*}
  We have $\nu_p(1^k + \dots + t^k) \ge \nu_p(t) - 1$ for any $k$, $t$, $p$.
\end{corollary*}
\begin{proof}
  Assume $p \mid t$.
  Handle the terms in that sum divisible by $p$ (by induction)
  and apply the lemma a bunch of times.
\end{proof}

Now the idea is to add primes $q$ one at a time to $n$, starting from the base case $n = p^e$.
So, formally we proceed by induction on the number of prime divisors of $n$.
We'll also assume $k \ge 1$ in what follows since the base case $k=0$ is easy.

\begin{itemize}
\ii First, suppose we want to go from $n$ to $nq$ where $q \nmid n$.
In that case $\varphi(nq)$ gained $\nu_p(q-1)$ factors of $p$
and then we need to show $\nu_p(S(nq,k)) \ge \nu_p(\varphi(n)) + \nu_p(q-1)$.
The trick is to write
\[ A(nq) = \left\{ a + nh \mid a \in A(n)
    \text{ and } h = 0,\dots,q-1 \right\}
    \setminus qA(n)  \]
and then expand using binomial theorem:
\begin{align*}
  S(nq, k) &= \sum_{a \in A(n)} \sum_{h=0}^{q-1} (a+nh)^k - \sum_{a \in A(n)} (qa)^k \\
  &= -q^k S(n,k) + \sum_{a \in A(n)} \sum_{h=0}^{q-1} \sum_{j=0}^k
    \left[ \binom kj a^{k-j} n^j h^j \right] \\
  &= -q^k S(n,k) +
    \sum_{j=0}^k \left[ \binom kj n^j \left( \sum_{a \in A(n)} a^{k-j} \right)
    \left( \sum_{h=0}^{q-1} h^j \right) \right] \\
  &= -q^k S(n,k) + \sum_{j=0}^k \left[ \binom kj n^j S(n,k-j)
    \left( \sum_{h=1}^{q-1} h^j \right) \right] \\
  &= (q-q^k) S(n,k)
    + \sum_{j=1}^k \left[ \binom kj n^j S(n,k-j)
    \left( \sum_{h=1}^{q-1} h^j \right) \right].
\end{align*}
We claim every term here has enough powers of $p$.
For the first term, $S(n,k)$ has at least $\nu_p(\varphi(n))$ factors of $p$;
and we have the $q-q^k$ multiplier out there.
For the other terms, we apply induction to $S(n,k-j)$;
moreover $\sum_{h=1}^{q-1} h^j$ has at least $\nu_p(q-1)-1$ factors of $p$ by corollary,
and we get one more factor of $p$ (at least) from $n^j$.

\ii On the other hand, if $q$ already divides $n$, then this time
\[ A(nq) = \left\{ a + nh \mid a \in A(n)
    \text{ and } h = 0,\dots,q-1 \right\}.  \]
and we have no additional burden of $p$ to deal with; the same calculation gives
\[ S(nq,k) = qS(n,k)
  + \sum_{j=1}^k \left[ \binom kj n^j S(n,k-j)
  \left( \sum_{h=1}^{q-1} h^j \right) \right] \]
which certainly has enough factors of $p$ already.
\end{itemize}

\begin{remark*}
  A curious bit about the problem is that $\nu_p(\varphi(n))$ can exceed $\nu_p(n)$,
  and so it is not true that the residues of $A(n)$ are well-behaved modulo $\varphi(n)$.

  As an example, let $n = 2 \cdot 3 \cdot 7 \cdot 13 = 546$,
  so $m = \varphi(n) = 1 \cdot 2 \cdot 6 \cdot 12 = 144$.
  Then $A(n)$ contains $26$ elements which are $1 \bmod 9$
  and $23$ elements which are $4 \bmod 9$.
\end{remark*}

\begin{remark*}
  The converse of the problem is true too
  (but asking both parts would make this too long for exam).
\end{remark*}