Mock AIME 3 Pre 2005 Problems/Problem 10
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 |