Maths Olympiad Prep

Library / /803 of 860

Number theory Difficulty 5.6 AIME, harder Find the answer

Define a power cycle to be a set SS consisting of the nonnegative integer powers of an integer aa, i.e. S={1,a,a2,}S=\left\{1, a, a^{2}, \ldots\right\} for some integer aa. What is the minimum number of power cycles required such that given any odd integer nn, there exists some integer kk in one of the power cycles such that nkn \equiv k (mod1024)?(\bmod 1024) ?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Partition the odd residues mod 1024 into 10 classes: Class 1: 1(mod4)1(\bmod 4). Class n(2n9):2n1(mod2n+1)n(2 \leq n \leq 9): 2^{n}-1\left(\bmod 2^{n+1}\right). Class 10: 1(mod1024)-1(\bmod 1024). Let SaS_{a} be the power cycle generated by aa. If aa is in class 1, all of SaS_{a} is in class 1. If a is in class nn (2n9)(2 \leq n \leq 9), then SaS_{a} is in the union of class nn and the residues 1(mod2n+1)1\left(\bmod 2^{n+1}\right). If aa is in class 10, then SaS_{a} is in the union of class nn and the residues 1(mod1024)1(\bmod 1024). Therefore, SaS_{a} cannot contain two of the following residues: 5,221,231,21015,2^{2}-1,2^{3}-1, \ldots 2^{10}-1, and that at least 10 cycles are needed. Note that 51281=(51)(5+1)(52+1)(564+1)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 52561=(51281)(5128+1)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 50,51,52555^{0}, 5^{1}, \ldots 5^{255}, the ratio between any two is a positive power of 5 smaller than 52565^{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 S5S_{5} contains members congruent to each element of class 1. Similarly, let 2n92 \leq n \leq 9. Then the order of aa, where a=2n1a=2^{n}-1, is 210n2^{10-n}. The 29n2^{9-n} terms a1,a3,a210n1a^{1}, a^{3}, \ldots a^{2^{10-n}-1} are pairwise not congruent and all in class nn. Class nn only has 29n2^{9-n} members, so SaS_{a} contains members congruent to each element of class nn. Finally, S1S_{-1} contains members congruent to the element of class 10. The cycles S5,S1S_{5}, S_{-1}, and 8 cycles SaS_{a} cover all the residues mod1024\bmod 1024, so the answer is 10.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.