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

Difference between revisions of "2001 AIME II Problems/Problem 10"

m
m (→‎Solution 2)
 
(9 intermediate revisions by 8 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
How many positive integer multiples of 1001 can be expressed in the form <math>10^{j} - 10^{i}</math>, where <math>i</math> and <math>j</math> are integers and <math>0\leq i < j \leq 99</math>?
+
How many positive integer multiples of <math>1001</math> can be expressed in the form <math>10^{j} - 10^{i}</math>, where <math>i</math> and <math>j</math> are integers and <math>0\leq i < j \leq 99</math>?
  
−
== Solution ==
+
== Solution 1 ==
−
{{solution}}
+
The [[prime factorization]] of <math>1001 = 7\times 11\times 13</math>. We have <math>7\times 11\times 13\times k = 10^j - 10^i = 10^i(10^{j - i} - 1)</math>. Since <math>\text{gcd}\,(10^i = 2^i \times 5^i, 7 \times 11 \times 13) = 1</math>, we require that <math>1001 = 10^3 + 1 | 10^{j-i} - 1</math>. From the factorization <math>10^6 - 1 = (10^3 + 1)(10^{3} - 1)</math>, we see that <math>j-i = 6</math> works; also, <math>a-b | a^n - b^n</math> implies that <math>10^{6} - 1 | 10^{6k} - 1</math>, and so any <math>\boxed{j-i \equiv 0 \pmod{6}}</math> will work.
 +
 
 +
<!-- I cannot make sense of this, so I commented it: - azjps - we require that <math>10^{j - i} - 1\equiv 0 \mod 1001</math>. By [[Euler's totient theorem]], <math>j - i\equiv 0\mod 6</math>. -->
 +
To show that no other possibilities work, suppose <math>j-i \equiv a \pmod{6},\ 1 \le a \le 5</math>, and let <math>j-i-a = 6k</math>. Then we can write <math>10^{j-i} - 1 = 10^{a} (10^{6k} - 1) + (10^{a} - 1)</math>, and we can easily verify that <math>10^6 - 1 \nmid 10^a - 1</math> for <math>1 \le a \le 5</math>.
 +
 
 +
If <math>j - i = 6, j\leq 99</math>, then we can have solutions of <math>10^6 - 10^0, 10^7 - 10^1, \dots\implies 94</math> ways. If <math>j - i = 12</math>, we can have the solutions of <math>10^{12} - 10^{0},\dots\implies 94 - 6 = 88</math>, and so forth. Therefore, the answer is <math>94 + 88 + 82 + \dots + 4\implies 16\left(\dfrac{98}{2}\right) = \boxed{784}</math>.
 +
 
 +
== Solution 2 ==
 +
Observation: We see that there is a pattern with <math>10^k \pmod{1001}</math>.
 +
<cmath>10^0 \equiv 1 \pmod{1001}</cmath>
 +
<cmath>10^1 \equiv 10 \pmod{1001}</cmath>
 +
<cmath>10^2 \equiv 100 \pmod{1001}</cmath>
 +
<cmath>10^3 \equiv -1 \pmod{1001}</cmath>
 +
<cmath>10^4 \equiv -10 \pmod{1001}</cmath>
 +
<cmath>10^5 \equiv -100 \pmod{1001}</cmath>
 +
<cmath>10^6 \equiv 1 \pmod{1001}</cmath>
 +
<cmath>10^7 \equiv 10 \pmod{1001}</cmath>
 +
<cmath>10^8 \equiv 100 \pmod{1001}</cmath>
 +
 
 +
So, this pattern repeats every 6.
 +
 
 +
Also, <math>10^j-10^i \equiv 0 \pmod{1001}</math>, so
 +
<math>10^j \equiv 10^i \pmod{1001}</math>, and thus, <cmath>j \equiv i \pmod{6}</cmath>. Continue with the 2nd paragraph of solution 1, and we get the answer of <math>\boxed{784}</math>.
 +
 
 +
-AlexLikeMath
 +
 
 +
==Solution 3==
 +
 
 +
Note that <math>1001=7\cdot 11\cdot 13,</math> and note that <math>10^3 \equiv \pmod{p}</math> for prime <math>p | 1001</math>; therefore, the order of 10 modulo <math>7,11</math>, and <math>13</math> must divide 6. A quick check on 7 reveals that it is indeed 6. Therefore we note that <math>i-j=6k</math> for some natural number k. From here, we note that for <math>j=0,1,2,3,</math> we have 16 options and we have 15,14,...,1 option(s) for the next 90 numbers (6 each), so our total is <math>4\cdot 16 + 6 \cdot \frac{15 \cdot 16}{2} = \boxed{784}</math>.
 +
 
 +
~Dhillonr25
 +
 
 +
==Solution 4==
 +
 
 +
<math>10^j - 10^i \equiv 0 \pmod{1001} \iff 10^{j - i} - 1 \equiv 0 \pmod{1001} \iff 10^{j - i} \equiv 1 \pmod{1001} \iff j \equiv i \pmod 6</math>. If <math>j \equiv i \equiv n \pmod 6</math> for <math>n = 0, 1, 2, 3</math>, there are <math>17</math> choices for each value of <math>n</math>, yielding <math>4 \cdot \dbinom{17}{2} = 544</math>. However, if <math>n = 4, 5</math>, there are only <math>16</math> choices, giving us <math>2 \cdot \dbinom{16}{2} = 240</math>. So, our final answer is <math>544 + 240 = \boxed{784}</math>.
 +
~Puck_0
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2001|n=II|num-b=9|num-a=11}}
 
{{AIME box|year=2001|n=II|num-b=9|num-a=11}}
 +
 +
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 22:16, 19 January 2024

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 1

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, 7 \times 11 \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}$.

Solution 2

Observation: We see that there is a pattern with $10^k \pmod{1001}$. \[10^0 \equiv 1 \pmod{1001}\] \[10^1 \equiv 10 \pmod{1001}\] \[10^2 \equiv 100 \pmod{1001}\] \[10^3 \equiv -1 \pmod{1001}\] \[10^4 \equiv -10 \pmod{1001}\] \[10^5 \equiv -100 \pmod{1001}\] \[10^6 \equiv 1 \pmod{1001}\] \[10^7 \equiv 10 \pmod{1001}\] \[10^8 \equiv 100 \pmod{1001}\]

So, this pattern repeats every 6.

Also, $10^j-10^i \equiv 0 \pmod{1001}$, so $10^j \equiv 10^i \pmod{1001}$, and thus, \[j \equiv i \pmod{6}\]. Continue with the 2nd paragraph of solution 1, and we get the answer of $\boxed{784}$.

-AlexLikeMath

Solution 3

Note that $1001=7\cdot 11\cdot 13,$ and note that $10^3 \equiv \pmod{p}$ for prime $p | 1001$; therefore, the order of 10 modulo $7,11$, and $13$ must divide 6. A quick check on 7 reveals that it is indeed 6. Therefore we note that $i-j=6k$ for some natural number k. From here, we note that for $j=0,1,2,3,$ we have 16 options and we have 15,14,...,1 option(s) for the next 90 numbers (6 each), so our total is $4\cdot 16 + 6 \cdot \frac{15 \cdot 16}{2} = \boxed{784}$.

~Dhillonr25

Solution 4

$10^j - 10^i \equiv 0 \pmod{1001} \iff 10^{j - i} - 1 \equiv 0 \pmod{1001} \iff 10^{j - i} \equiv 1 \pmod{1001} \iff j \equiv i \pmod 6$. If $j \equiv i \equiv n \pmod 6$ for $n = 0, 1, 2, 3$, there are $17$ choices for each value of $n$, yielding $4 \cdot \dbinom{17}{2} = 544$. However, if $n = 4, 5$, there are only $16$ choices, giving us $2 \cdot \dbinom{16}{2} = 240$. So, our final answer is $544 + 240 = \boxed{784}$. ~Puck_0

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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