Difference between revisions of "Mock AIME 3 Pre 2005 Problems/Problem 10"
(No difference)
|
Revision as of 10:25, 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 .