Problem

Source: 2018 USAMO 3, by Ivan Borsenco

Tags: USAMO, 2018 USAMO Problem 3, number theory, Hi



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$. Proposed by Ivan Borsenco