2002 AIME II Problems/Problem 7
It is known that, for all positive integers ,
Find the smallest positive integer such that is a multiple of .
is a multiple of if is a multiple of . So .
Since is always odd, and only one of and is even, either .
If , then . If , then . If , then .
Thus, there are no restrictions on in .
It is easy to see that only one of , , and is divisible by . So either .
From the Chinese Remainder Theorem, . Thus, the smallest positive integer is .
To elaborate, we write out all 6 possibilities of parings. For example, we have
is one pairing, and
is another. We then solve this by writing the first as and then move the 15 to get .
We then list out all the mods of the multiples of , and realize that each of these pairings can be generalized to become one of these multiples of .
The chain is as follows:
and then it loops.
We see that for the first equation we have at the 24th position, so we then do to get the first answer of 399.
Again, this is possible to repeat for all cases. CRT guarantees that we will have a solution before or and indeed we did :P
|2002 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|