Problem:
There are exactly K positive integers b with 5≤b≤2024 such that the base- b integer 2024b​ is divisible by 16 (where 16 is in base ten). What is the sum of the digits of K ?
Answer Choices:
A. 16
B. 17
C. 18
D. 20
E. 21
Solution:
Notice that 2024b​=2b3+2b+4=2(b+1)(b2−b+2), and consider the residue classes of this number modulo 8 . If b≡7(mod8), then b+1≡0(mod8), and if b≡3 or 6 (mod8), then b2−b+2≡0(mod8). In each case 2024b​ is divisible by 16 .
In all other cases 2024b​ is not divisible by 16 . Indeed, if b≡0,2, or 4(mod8), then b+1 is odd, and b2−b+2≡b+2(mod8), so 2024b​ is divisible by no power of 2 greater than 23. If b≡1 or 5(mod8), then b+1 and b2−b+2 are both odd multiples of 2 , so 2024b​ is divisible by 8 , but not by 16 .
Because 2024=253⋅8, there are 253⋅3=759 positive integers b≤2024 that are congruent to 3 , 6 , or 7 modulo 8 . The number 3 must be excluded from this total, because the problem statement requires b to be at least 5 . Thus K=759−1=758, and the sum of the digits of K is 7+5+8=(D)20​.
The problems on this page are the property of the MAA's American Mathematics Competitions