Difference between revisions of "2001 AIME II Problems/Problem 10"
(fix) |
|||
| 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 == | ||
| − | + | 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, 3 \times 7 \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>. | ||
== 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]] | ||
Revision as of 14:16, 26 July 2008
Problem
How many positive integer multiples of 
can be expressed in the form 
, where 
and 
are integers and 
?
Solution
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 
.
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 | ||
