2002 AIME II Problems/Problem 7
Contents
Problem
It is known that, for all positive integers ,
Find the smallest positive integer such that is a multiple of .
Solution
is a multiple of if is a multiple of . So .
Since is always odd, and only one of and is even, either .
Thus, .
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 .
Thus, .
From the Chinese Remainder Theorem, . Thus, the smallest positive integer is .
Addition 9/23/17
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 16, and realize that each of these 6 pairings can be generalized to become one of these multiples of 16.
The chain is as follows:
7, 23, 14, 5, 21, 12, 3, 19, 10, 1, 17, 8, 24, 15, 6, 22, 13, 4, 20, 11, 27, 18, 9, 0, and then it loops.
We see that for the first equation we have 9 mod 25 at the 21st position, so we then do to get the first answer of 399.
Again, this is possible to repeat for all 6 cases. CRT guarantees that we will have a solution before 25*16 or 400 and indeed we did :P
See also
2002 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
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.