Problem

Source: Iran 3rd round 2011-number theory exam-p2

Tags: induction, algebra, polynomial, modular arithmetic, calculus, integration, function



Let $n$ and $k$ be two natural numbers such that $k$ is even and for each prime $p$ if $p|n$ then $p-1|k$. let $\{a_1,....,a_{\phi(n)}\}$ be all the numbers coprime to $n$. What's the remainder of the number $a_1^k+.....+a_{\phi(n)}^k$ when it's divided by $n$? proposed by Yahya Motevassel