Difference between revisions of "2001 AIME II Problems/Problem 10"
Line 3: | Line 3: | ||
== 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, | + | 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>. --> | <!-- 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>. --> |
Revision as of 13:13, 3 October 2018
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.