Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2001 AIME II Problems/Problem 10: Difference between revisions

← Older editNewer edit →
fix
Nathan wailes (talk | contribs)
2,960 edits
No edit summary
Line 14: Line 14:


[[Category:Intermediate Number Theory Problems]]
[[Category:Intermediate Number Theory Problems]]
{{MAA Notice}}

Revision as of 19:35, 4 July 2013

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

The prime factorization of $1001 = 7\times 11\times 13$. We have $7\times 11\times 13\times k = 10^j - 10^i = 10^i(10^{j - i} - 1)$. Since $\text{gcd}\,(10^i = 2^i \times 5^i, 3 \times 7 \times 13) = 1$, we require that $1001 = 10^3 + 1 | 10^{j-i} - 1$. From the factorization $10^6 - 1 = (10^3 + 1)(10^{3} - 1)$, we see that $j-i = 6$ works; also, $a-b | a^n - b^n$ implies that $10^{6} - 1 | 10^{6k} - 1$, and so any $\boxed{j-i \equiv 0 \pmod{6}}$ will work.

To show that no other possibilities work, suppose $j-i \equiv a \pmod{6},\ 1 \le a \le 5$, and let $j-i-a = 6k$. Then we can write $10^{j-i} - 1 = 10^{a} (10^{6k} - 1) + (10^{a} - 1)$, and we can easily verify that $10^6 - 1 \nmid 10^a - 1$ for $1 \le a \le 5$.

If $j - i = 6, j\leq 99$, then we can have solutions of $10^6 - 10^0, 10^7 - 10^1, \dots\implies 94$ ways. If $j - i = 12$, we can have the solutions of $10^{12} - 10^{0},\dots\implies 94 - 6 = 88$, and so forth. Therefore, the answer is $94 + 88 + 82 + \dots + 4\implies 16\left(\dfrac{98}{2}\right) = \boxed{784}$.

See also

2001 AIME II (Problems • Answer Key • Resources)
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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_II_Problems/Problem_10&oldid=55343"