2001 AIME II Problems/Problem 10
How many positive integer multiples of can be expressed in the form , where and are integers and ?
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 .
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
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 .
|2001 AIME II (Problems • Answer Key • Resources)|
|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.