Difference between revisions of "2001 AIME II Problems/Problem 10"
m (→Solution 2) |
|||
(8 intermediate revisions by 7 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 == |
− | + | 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. | |
− | If <math>j - i = 12</math>, we can have the solutions of <math>10^{12} - 10^{0},\dots\implies 94 - 6 = 88</math>. | + | |
+ | <!-- 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 can be expressed in the form , where and are integers and ?
Solution 1
The prime factorization of . We have . Since , we require that . From the factorization , we see that works; also, implies that , and so any will work.
To show that no other possibilities work, suppose , and let . Then we can write , and we can easily verify that for .
If , then we can have solutions of ways. If , we can have the solutions of , and so forth. Therefore, the answer is .
Solution 2
Observation: We see that there is a pattern with .
So, this pattern repeats every 6.
Also, , so , and thus, . Continue with the 2nd paragraph of solution 1, and we get the answer of .
-AlexLikeMath
Solution 3
Note that and note that for prime ; therefore, the order of 10 modulo , and must divide 6. A quick check on 7 reveals that it is indeed 6. Therefore we note that for some natural number k. From here, we note that for we have 16 options and we have 15,14,...,1 option(s) for the next 90 numbers (6 each), so our total is .
~Dhillonr25
Solution 4
. If for , there are choices for each value of , yielding . However, if , there are only choices, giving us . So, our final answer is . ~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.