Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 10"
Line 32: | Line 32: | ||
<math>\sum_{k=0}^{3n} \begin{pmatrix} 3n \\ 3k \end{pmatrix}=\frac{2^{3n}+q(n)}{3}</math> | <math>\sum_{k=0}^{3n} \begin{pmatrix} 3n \\ 3k \end{pmatrix}=\frac{2^{3n}+q(n)}{3}</math> | ||
+ | When <math>n</math> is odd, <math>3n</math> is odd, <math>2^{odd} \equiv (-1)^{odd}\;(mod\;3)\equiv (-1)^{odd}\;(mod\;3)</math> | ||
== See also == | == See also == |
Revision as of 10:52, 25 November 2023
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.
When is odd, is odd,
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 |