Mock AIME 4 2006-2007 Problems/Problem 10
Problem
Compute the remainder when
is divided by 1000.
Solution
Let and be the two complex third-roots of 1. Then let
.
Now, if is a multiple of 3, . If is one more than a multiple of 3, . If is two more than a multiple of 3, . Thus
, which is exactly three times our desired expression.
We also have an alternative method for calculating : we know that , so . Note that these two numbers are both cube roots of -1, so .
Thus, the problem is reduced to calculating . , so we need to find and then use the Chinese Remainder Theorem. Since , by Euler's Totient Theorem . Combining, we have , and so .
See also
Mock AIME 4 2006-2007 (Problems, Source) | ||
Preceded by Problem 9 |
Followed by Problem 11 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 |