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:
Answer (363):
For each n let anβ=23bnβ. Then bnβ is the least positive integer satisfying
23bnββ‘1(mod2n)
Note that bnβ is the (unique) inverse of 23 modulo 2n, chosen to lie in the range [0,2nβ1]. For convenience, let b0β=0, and note that b1β=1. Because 23bnββ‘1(mod2n), either 23bnββ‘1(mod2n+1) or 23bnββ‘1+2n(mod2n+1). In the first case bn+1β=bnβ, and in the second case 23(bnβ+2n)β‘1(mod2n+1), so bn+1β=bnβ+2n.
Let s2β denote the binary sum of bits function. Because bnβ<2n for all n,
s2β(bn+1β)βs2β(bnβ)={10β if bn+1βξ =bnβ if bn+1β=bnββ
In particular, letting N denote the required answer and summing the above equation over 0β€nβ€1000 gives 1001βN=s2β(b1001β)βs2β(b0β), so N=1001βs2β(b1001β). Now it suffices to find b1001β. By Fermat's Little Theorem, 222β1 is a multiple of 23 , and because 222β1=(211β1)(211+1), either 211β1 or 211+1 is divisible by 23 . In fact, 211β1=23β
89.
Let C=89(2990+2979+β―+211+1). Note that
23Cβ=23β
89(2990+2979+β―+211+1)=(211β1)(2990+2979+β―+211+1)=21001β1β‘β1(mod21001)β
so 23(21001βC)β‘1(mod21001). This, along with 0β€21001βCβ€21001β1, implies that b1001β=21001βC.
The binary representation of C, when padded with leading zeros, consists of 91 blocks of length 11 , each equal to 89=00001011001two β. Thus s2β(C)=91β
4=364. Let D=21001βC and consider the addition C+D in binary. Because this sum equals 21001, a total of 1001 carries must have taken place, so s2β(C)+s2β(D)=s2β(21001)+1001, which is equivalent to s2β(D)=1002βs2β(C). Therefore N=1001βs2β(D)=s2β(C)β1=363.
OR
Because anββ‘1(mod2n), it follows that anβ=kβ
2n+1 for some positive integer k. For a fixed positive integer n, consider the 23 numbers rkβ=kβ
2n+1 with 0β€kβ€22. Because rsββrtβ=(sβt)β
2n is not a multiple of 23 when sξ =t, it follows that the 23 numbers rkβ give 23 different remainders modulo 23 , and hence exactly one of the rkβ is a multiple of 23 and is equal to anβ. Because 23β£211β1, it follows that for all positive integers k and n,
kβ
2n+1β‘kβ
2n+11+1(mod23)
Therefore anβ=an+1β if and only if an+11β=an+12β. Computing anβ for nβ€12 gives
βa1β=23=1+11β
21a2β=a1β+23β
21=1+17β
22a3β=a2β+23β
22=1+(17+23)β
22=1+5β
25=a4β=a5βa6β=a5β+23β
25=1+28β
25=1+7β
27=a7βa8β=a7β+23β
27=1+15β
28a9β=a8β+23β
28=1+19β
29a10β=a9β+23β
29=1+21β
210a11β=a10β+23β
210=1+11β
212=a12β.β
Hence there are 4 positive integers nβ€11 such that anβ=an+1β. It follows that there are 4β
90=360 positive integers nβ€990 such that anβ=an+1β. In addition, there are 3 more integers n such that 990<nβ€1000 and anβ=an+1β for a total of 363 integers.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions