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 three that satisfies anββ‘1mod2n, 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β+1β‘0mod23β2nqnββ‘β1mod23
Let's first find the order of 2 mod 23. Notice that 223β1β‘1mod23 but
211β‘1mod23
Thus the order of 2 mod 23 is 1.
Notice how we can reduce this expression to
2nqnββ‘β1mod23β2nmod11qnββ‘β1mod23
We simply have to do casework over cycles now, as the residue of n mod 11 determines the specific value of qnβ.
Suppose 11β£n, this yields qnβ=22,bnβ=1.
Suppose nβ‘1mod11, this yields qnβ=11,bnβ=1.
Doing these for all residues of n mod 11 yields that the only residues for which bnβ=bn+1β and subsequently anβ=an+1β are nβ‘0,3,4,6mod11.
We also note that "wrapping around", when nβ‘10mod11 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
{1,2,3,...,11}
{12,13,...,22}
all the way to
{981,982,...,990}
or 90 sets that each yield 4 valid solutions, and from
{991,992,...,1000} there are 3, so the answer is
90β
4+3=363β
The problems on this page are the property of the MAA's American Mathematics Competitions