Skip to main content

2021 Fall AMC 12B Problem 25

Problem 25 of 25HarderNumber Theory

For nn a positive integer, let R(n)R(n) be the sum of the remainders when nn is divided by 2,2, 3,3, 4,4, 5,5, 6,6, 7,7, 8,8, 9,9, and 10.10. For example, R(15)=1+0+3+0+3+1+7+6+5=26. \begin{aligned} &R(15) = 1 + 0 + 3 + 0 + 3 \\ &\quad {}+ 1 + 7 + 6 + 5 = 26. \end{aligned} How many two-digit positive integers nn satisfy R(n)=R(n+1)?R(n) = R(n + 1)?

Answer choices

Show solution

Solution

Going from nn to n+1,n + 1, each remainder nmodmn \bmod m increases by 11 unless n+1n + 1 is divisible by m,m, in which case it drops from m1m - 1 to 0.0. So R(n+1)R(n)=92m10mn+1m. \begin{aligned} &R(n+1) - R(n) \\ &= 9 - \sum_{\substack{2 \le m \le 10 \\ m \mid n+1}} m. \end{aligned} Distinct integers from 22 through 1010 can sum to 99 only as {9},{2,7},{3,6},{4,5},\{9\},\{2,7\},\{3,6\},\{4,5\}, or {2,3,4}.\{2,3,4\}. Divisibility closure eliminates every case except {2,7}:\{2,7\}: for example, a multiple of 99 also has divisor 3,3, and a multiple of 66 also has divisors 22 and 3.3. Thus n+1n+1 must be a multiple of 1414 with no other divisor in {2,,10}.\{2,\ldots,10\}. Testing the multiples 14,28,42,56,70,84,9814,28,42,56,70,84,98 in the required range leaves only 1414 and 98.98. Hence n=13n=13 or n=97,n=97, giving 22 values. Thus, the correct answer is C.

More practice

Concepts: modular arithmetic · divisibility

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.