USAMO 2018 — Days 1 and 2 Question 3

Let $n\ge2$, and let $a_1,\ldots,a_m$ be the $m=\varphi(n)$ positive integers less than $n$ and relatively prime to $n$. Suppose every prime divisor of $m$ divides $n$. Prove $m\mid a_1^k+\cdots+a_m^k$ for every integer $k\gt 0$.

Proposed by Ivan Borsenco. Source: Evan Chen’s third-party compilation, not an official publication. One editorial point; manual grading only.