Solution November 18, 2007

Problem

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}

Solution

Let A := \{a_{1},a_{2},\dots,a_{\varphi(n)}\}. Modulo n\,, we have A = 2A\,, because 2\, is coprime to n\,. Therefore,

S := a_{1}^{1386}+a_{2}^{1386}+\dots+a_{\varphi(n)}^{1386} \equiv (2a_{1})^{1386}+(2a_{2})^{1386}+\dots+(2a_{\varphi(n)})^{1386} \pmod n
S = 2^{1386} S \pmod n\,
S (2^{1386}-1) = 0 \pmod n\,

But n\, is also coprime to 2^{1386}-1\, so we can divide that equivalence by 2^{1386}-1\,. This gives

S = 0 \pmod n\,

which is what we wanted to prove.\square