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$

Retrieved from "https://www.efnet-math.org:443/w/Solution_November_18%2C_2007"