Difference between revisions of "Mock AIME 3 Pre 2005 Problems/Problem 10"
Line 33: | Line 33: | ||
Therefore we have <math>a_n \equiv 6\cdot 16 - 4^2 - 4\cdot 4 - 6 = \boxed{058} \pmod{1000}</math>. | Therefore we have <math>a_n \equiv 6\cdot 16 - 4^2 - 4\cdot 4 - 6 = \boxed{058} \pmod{1000}</math>. | ||
− | ==See | + | ==See Also== |
+ | {{Mock AIME box|year=Pre 2005|n=3|num-b=9|num-a=11}} |
Latest revision as of 10:36, 4 April 2012
Problem
is a sequence of positive integers such that
for all integers . Compute the remainder obtained when
is divided by
if
.
Solution
We can easily express as the following sum:
This can be broken down into three simpler sums:
Using finite calculus, one can easily derive the following classical sums:
Using these, we can now compute:
And hence we get the closed form for :
Now we can compute as follows:
We know that (where
is the Euler's totient function), hence
, and thus
. Thus there is an integer
such that
. And then
, hence
.
Therefore we have .
See Also
Mock AIME 3 Pre 2005 (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 |