Problem:
For each positive integer n let anβ be the least positive integer multiple of 23 such that anββ‘1(mod2n). Find the number of positive integers n less than or equal to 1000 that satisfy anβ=an+1β.
Solution:
Since anβ is the least multiple of 23 that satisfies anββ‘1(mod2n), we can create a sequence b such that bnβ=23anββ and anβ=23bnβ=2nqnβ+1 for the least integer qnβ.
Notice that this means that
2nqnβ+12nqnβββ‘0(mod23)β‘β1(mod23).β
Let's first find the order of 2(mod23). Notice that by Fermat's Little Theorem, 222β‘1(mod23), but more specifically, 211β‘1(mod23). Thus the order of 2(mod23) is 11.
Notice how we can reduce this expression to
2nqnβ2n(mod11)qnβββ‘β1(mod23)β‘β1(mod23).β
We simply have to do casework over cycles now, as the residue of n(mod11) determines the specific value of qnβ.
Suppose 11β£n, this yields qnβ=22 and bnβ=1.
Suppose nβ‘1(mod11), this yields qnβ=11 and bnβ=1.
Doing these for all residues of n(mod11) yields that the only residues for which bnβ=bn+1β and subsequently anβ=an+1β are nβ‘0,3,4,6(mod11).
We also note that "wrapping around", when nβ‘10(mod11) that bnβξ =bn+1β so the only things that we have to count for this problem are the number of times these residues repeat.
We have the sets {1,2,3,β¦,11}, {12,13,β¦,22}, all the way to {981,982,β¦,990}. There are 90 such sets that each yield 4 valid solutions. From the set {991,992,β¦,1000} there are 3 solutions. So the answer is
90β
4+3=363β.
The problems on this page are the property of the MAA's American Mathematics Competitions