Let $n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}\ge2$. If for any $\alpha\in\mathbb N$, $p_i-1\nmid\alpha$, where $i=1,2,\ldots,s$, prove that $n\mid\sum_{\alpha\in\mathbb Z^*_n}\alpha^{\alpha}$ where $\mathbb Z^*_n=\{a\in\mathbb Z_n:\gcd(a,n)=1\}$.
Source: Mongolian MO 2007 Teachers P6
Tags: number theory
Let $n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}\ge2$. If for any $\alpha\in\mathbb N$, $p_i-1\nmid\alpha$, where $i=1,2,\ldots,s$, prove that $n\mid\sum_{\alpha\in\mathbb Z^*_n}\alpha^{\alpha}$ where $\mathbb Z^*_n=\{a\in\mathbb Z_n:\gcd(a,n)=1\}$.