Define a power cycle to be a set consisting of the nonnegative integer powers of an integer , i.e. for some integer . What is the minimum number of power cycles required such that given any odd integer , there exists some integer in one of the power cycles such that
Solution
Partition the odd residues mod 1024 into 10 classes: Class 1: . Class . Class 10: . Let be the power cycle generated by . If is in class 1, all of is in class 1. If a is in class , then is in the union of class and the residues . If is in class 10, then is in the union of class and the residues . Therefore, cannot contain two of the following residues: , and that at least 10 cycles are needed. Note that has exactly 9 factors of 2 in its prime factorization, while 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 , the ratio between any two is a positive power of 5 smaller than , 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 contains members congruent to each element of class 1. Similarly, let . Then the order of , where , is . The terms are pairwise not congruent and all in class . Class only has members, so contains members congruent to each element of class . Finally, contains members congruent to the element of class 10. The cycles , and 8 cycles cover all the residues , so the answer is 10.