2001 AIME II Problem 10

Attempt Problem 10 of the 2001 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2001 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

10.

How many positive integer multiples of 10011001 can be expressed in the form 10j10i,10^{j} - 10^{i}, where ii and jj are integers and 0i<j99?0 \le i \lt j \le 99?

Answer: 784
Concepts:multiplicative ordermodular arithmeticcounting pairs
Difficulty rating: 2710
Solution:

Factor 10j10i=10i(10ji1).10^j - 10^i = 10^i(10^{j-i} - 1). Since 1001=711131001 = 7 \cdot 11 \cdot 13 is coprime to 10i,10^i, we need 100110ji1.1001 \mid 10^{j-i} - 1. The multiplicative order of 1010 is 66 modulo 7,7, 22 modulo 11,11, and 66 modulo 13,13, so 10k1(mod1001)10^k \equiv 1 \pmod{1001} exactly when kk is a multiple of 6.6. Distinct pairs (i,j)(i, j) give distinct values, so we just count the pairs.

For ji=6dj - i = 6d with 1d16,1 \le d \le 16, the index ii can be 0,1,,996d,0, 1, \ldots, 99 - 6d, giving 1006d100 - 6d choices. The total is d=116(1006d)=94+88++4=(94+4)162=784. \begin{aligned} &\sum_{d=1}^{16} (100 - 6d) \\ &= 94 + 88 + \cdots + 4 \\ &= \frac{(94 + 4) \cdot 16}{2} \\ &= 784. \end{aligned}

← Problem 9#9
Full Exam

Problem 10 in Other Years