HMMT February

Solution:

Answer: 10

Partition the odd residues mod 1024 into 10 classes:
- Class 1: $1 \pmod{4}$.
- Class $n$ $(2 \leq n \leq 9)$: $2^{n}-1 \pmod{2^{n+1}}$.
- Class 10: $-1 \pmod{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 \pmod{2^{n+1}}$. If $a$ is in class 10, then $S_{a}$ is in the union of class $n$ and the residues $1 \pmod{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)(5^{2}+1) \cdots (5^{64}+1)$ has exactly 9 factors of 2 in its prime factorization, while $5^{256}-1 = (5^{128}-1)(5^{128}+1)$ 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 mod 1024, so the answer is 10.

Solution:

Lemma. Given a positive integer $n \geq 3$, there exists an odd integer $x$ such that the order of $x$ modulo $2^{n}$ is $2^{n-2}$.

Proof. We apply induction on $n$. The base cases of $n=3,4$ are clearly true with $x=3$, so suppose we have the statement holds for $n-1$ and we wish to show it for $n$ where $n \geq 5$. Suppose no such integer $x$ exists, so we have $x^{2^{n-3}} \equiv 1 \pmod{2^{n}}$ for all odd $x$. But then remark that $(x^{2^{n-4}}-1)(x^{2^{n-4}}+1) \equiv 0 \pmod{2^{n}}$. As $n-4 \geq 1$ we have $x^{2^{n-4}}+1 \equiv 2 \pmod{4}$ as all squares are $1 \pmod{4}$, so it follows for the above relation to be true we require $2^{n-1}$ divides $x^{2^{n-4}}-1$ for all odd $x$. However, by taking $x$ to have order $2^{n-3}$ modulo $2^{n-1}$ (which exists by the inductive hypothesis) we get a contradiction so we are done.

Now, let $x$ have order $2^{8}$ modulo $2^{10}$. Remark that if for some integer $k$ we had $x^{k} \equiv -1 \pmod{2^{10}}$, we would have $x^{2k} \equiv 1 \pmod{2^{10}}$ so $2^{7} \mid k$. In that case $k$ is even so as $x$ is odd we have $x^{k} \equiv 1 \pmod{4}$ but $-1+1024m$ is never $1 \pmod{4}$ for any integer $m$ so it follows $-1$ is not equal to $x^{k}$ modulo 1024 for any integer $k$. Thus it follows that when we let $S$ to be the set of powers of $x$, then no two elements in $S$ and $-S$ are congruent modulo 1024. As the order of $x$ is 256 and there are 512 possible odd remainders upon dividing by 1024, it immediately follows that every integer $x$ is congruent modulo 1024 to $\pm x^{k}$ for some $1 \leq k \leq 256$ and some choice of sign.

Now, it is easy to see that $x, -x, -x^{2}, -x^{4}, \ldots, -x^{2^{7}}, -x^{2^{8}}$ generating 10 power cycles works ($x^{a}$ for any $a$ is in the first, and then $-x^{2^{k} a}$ for odd $a$ is in the power cycle generated by $-x^{2^{k}}$). To show that we cannot do any better suppose there exist 9 power cycles which include all odd integers modulo 1024. Then remark that $-x^{2^{k}}$ is congruent to a number in a power cycle modulo 1024 if and only if the power cycle is generated by an integer congruent to $x^{-2^{k} \cdot a} \pmod{1024}$ where $a$ is an odd integer. It follows that 9 integers must be congruent to $-x^{a_{1}}, -x^{2 a_{2}}, \ldots, -x^{256 a_{9}} \pmod{1024}$ for some odd integers $a_{1}, a_{2}, \ldots, a_{9}$. But then 3 is clearly not in any of the power cycles, contradiction so it follows we must have at least 10 power cycles so we are done.