# Remainders Of Powers Of 2

**Number Theory**Level 4

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.