Mock AIME 4 2006-2007 Problems/Problem 10
Contents
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 .
Solution 2
, and
where is an integer that depends on the value of and will make the sum an integer. The division by 3 comes from the fact that we're skipping 2 out of every 3 terms in the binomial. So we divide the whole sum by 3 and we add or subtract to correct for the integer based on the modularity of the sum with 3
When is odd, is odd, , Therefore because we need to subract 2.
When is even, is even, , Therefore because we need to add 2.
So, the equation becomes:
Therefore, the remainder when is divided by 1000 is
~Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
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 |