Problem

Source: Iranian National Olympiad (3rd Round) 2007

Tags: modular arithmetic, number theory proposed, number theory



Let $ n$ be a natural number, such that $ (n,2(2^{1386}-1))=1$. Let $ \{a_{1},a_{2},\dots,a_{\varphi(n)}\}$ be a reduced residue system for $ n$. Prove that:\[ n|a_{1}^{1386}+a_{2}^{1386}+\dots+a_{\varphi(n)}^{1386}\]