# Remainders Of Powers Of 2

For all $$n \in \mathbb{N},$$ let $$S_n$$ be the set of all possible remainders when a power of $$2$$, to a non-negative exponent, is divided by $$n.$$ Find the number of positive integers $$n \leq 1000$$ for which the sum of elements of $$S_n$$ is a multiple of $$n.$$

Details and assumptions

• $$1= 2^0$$ is a power of $$2$$ to a non-negative exponent.

• As an explicit example, when $$n=5,$$ we list down the first few residues of $$2^x \pmod{5}.$$ $\begin{array}{|c|c|c|} \hline x & 2^x & 2^x \pmod{5} \\ \hline 0 & 1 & 1 \\ \hline 1 & 2 & 2 \\ \hline 2 & 4 & 4 \\ \hline 3 & 8 & 3 \\ \hline 4 & 16 & 1 \\ \hline\end{array}$ The residues $$2^x \pmod{5}$$ become periodic from now on. Thus, $$S_n= \{1, 2, 4, 3\}.$$ The sum of elements of $$S_n$$ is $$1+2+4+3= 10,$$ which is a multiple of $$5.$$

• The elements of the set $$S_n$$ are distinct.

×