Problem 1463

Let $m > 2$ be a natural number and if $i \neq j$ then $a_i \neq a_j \pmod{m}$. Prove that if $(a_i, m) = 1$, $i = 1, \varphi(m)$ then there exists the permutation $b_1, b_2, ..., b_{\varphi(m)}$ of numbers $a_1, a_2, ..., a_{\varphi(m)}$ such that $a_1^{b_1} + a_2^{b_2} + ... + a_{\varphi(m)}^{b_{\varphi(m)}}$ is divisible by $m$.