HMMT February

Partition the odd residues mod 1024 into 10 classes: Class 1: $1(\bmod 4)$. Class $n(2 \leq n \leq 9): 2^{n}-1\left(\bmod 2^{n+1}\right)$. Class 10: $-1(\bmod 1024)$. Let $S_{a}$ be the power cycle generated by $a$. If $a$ is in class 1, all of $S_{a}$ is in class 1. If a is in class $n$ $(2 \leq n \leq 9)$, then $S_{a}$ is in the union of class $n$ and the residues $1\left(\bmod 2^{n+1}\right)$. If $a$ is in class 10, then $S_{a}$ is in the union of class $n$ and the residues $1(\bmod 1024)$. Therefore, $S_{a}$ cannot contain two of the following residues: $5,2^{2}-1,2^{3}-1, \ldots 2^{10}-1$, and that at least 10 cycles are needed. Note that $5^{128}-1=(5-1)(5+1)\left(5^{2}+1\right) \cdots\left(5^{64}+1\right)$ has exactly 9 factors of 2 in its prime factorization, while $5^{256}-1=\left(5^{128}-1\right)\left(5^{128}+1\right)$ is divisible by 1024 so the order of 5 modulo 1024, the smallest positive power of 5 that is congruent to 1, is 256. Observe that among $5^{0}, 5^{1}, \ldots 5^{255}$, the ratio between any two is a positive power of 5 smaller than $5^{256}$, so the ratio is not congruent to 1 and any two terms are not congruent mod 1024. In addition, all terms are in class 1, and class 1 has 256 members, so $S_{5}$ contains members congruent to each element of class 1. Similarly, let $2 \leq n \leq 9$. Then the order of $a$, where $a=2^{n}-1$, is $2^{10-n}$. The $2^{9-n}$ terms $a^{1}, a^{3}, \ldots a^{2^{10-n}-1}$ are pairwise not congruent and all in class $n$. Class $n$ only has $2^{9-n}$ members, so $S_{a}$ contains members congruent to each element of class $n$. Finally, $S_{-1}$ contains members congruent to the element of class 10. The cycles $S_{5}, S_{-1}$, and 8 cycles $S_{a}$ cover all the residues $\bmod 1024$, so the answer is 10.