Difference between revisions of "2001 AIME II Problems/Problem 10"
m |
|||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| − | {{ | + | Factoring <math>1001 = 7\times 11\times 13</math>. We have <math>7\times 11\times 13\times k = 10^j - 10^i\implies \dfrac{7(11)(13)(k)}{10^i} = 10^{j - i} - 1</math>. This means that <math>10^{j - i} - 1\equiv 0 \mod 1001</math>. By Euler's totient theorem, <math>j - i\equiv 0\mod 6</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>. |
| + | If <math>j - i = 12</math>, we can have the solutions of <math>10^{12} - 10^{0},\dots\implies 94 - 6 = 88</math>. Likewise, we have <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}} | ||
Revision as of 22:32, 25 March 2008
Problem
How many positive integer multiples of 1001 can be expressed in the form 
, where 
and 
are integers and 
?
Solution
Factoring 
. We have 
. This means that 
. By Euler's totient theorem, 
. If 
, then we can have solutions of 
.
If 
, we can have the solutions of 
. Likewise, we have 
.
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 | ||
