2001 AIME II Problems/Problem 10

Revision as of 21:32, 25 March 2008 by H34N1 (talk | contribs)

Problem

How many positive integer multiples of 1001 can be expressed in the form $10^{j} - 10^{i}$, where $i$ and $j$ are integers and $0\leq i < j \leq 99$?

Solution

Factoring $1001 = 7\times 11\times 13$. We have $7\times 11\times 13\times k = 10^j - 10^i\implies \dfrac{7(11)(13)(k)}{10^i} = 10^{j - i} - 1$. This means that $10^{j - i} - 1\equiv 0 \mod 1001$. By Euler's totient theorem, $j - i\equiv 0\mod 6$. If $j - i = 6, j\leq 99$, then we can have solutions of $10^6 - 10^0, 10^7 - 10^1, \dots\implies 94$. If $j - i = 12$, we can have the solutions of $10^{12} - 10^{0},\dots\implies 94 - 6 = 88$. Likewise, we have $94 + 88 + 82 + \dots + 4\implies 16\left(\dfrac{98}{2}\right) = \boxed{784}$.

See also

2001 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions