Mock AIME II 2012 Problems/Problem 3
Problem
Let be a recursion defined such that
, and
where
, and
is an integer. If
for
being a positive integer greater than
and
being a positive integer greater than 2, find the smallest possible value of
.
Solution
The sum of the digits when we get this down to a one digit number is the same thing as the number modulo 9. This is because let’s say we start with a number . When we take the sum of the digits modulo 9, this is the same thing as taking the number modulo 9. However, the sum of the digits modulo 9 is the same thing as the sum of the sum of the digits modulo 9, and this pattern repeats.
We are left with finding . Note that
, therefore we get
. By Euler’s Totient Theorem,
or
. We now need to find
, which is equal to
. Note that
, and
, so this pattern repeats
in the exponents. Since
, we get
. From this, we get
, so we need to find
. Since
, we get an answer of
.