Mock AIME II 2012 Problems/Problem 3

Problem

The $\textit{digital root}$ of a number is defined as the result obtained by repeatedly adding the digits of the number until a single digit remains. For example, the $\textit{digital root}$ of $237$ is $3$ ($2+3+7=12, 1+2=3$). Find the $\textit{digital root}$ of $2012^{2012^{2012}}$.

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 $n$. 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 $2012^{2012^{2012}}\pmod{9}$. Note that $2012=5\pmod{9}$, therefore we get $5^{2012^{2012}}\pmod{9}$. By Euler’s Totient Theorem, $5^{\phi(9)}\equiv 1\pmod{9}$ or $5^6\equiv 1\pmod{9}$. We now need to find $2012^{2012}\pmod{6}$, which is equal to $2^{2012}\pmod{6}$. Note that $2^1\equiv 2\pmod{6}, 2^2\equiv 4\pmod 6$, and $2^3\equiv 2\pmod 6$, so this pattern repeats $\pmod 2$ in the exponents. Since $2012\equiv 0\pmod2$, we get $2^{2012}\pmod 6\equiv 4\pmod 6$. From this, we get $2012^{2012}\pmod{6}\equiv 4\pmod{6}$, so we need to find $5^{4}\pmod{9}$. Since $5^4=625$, we get an answer of $6+2+5\pmod 9=\boxed{004}\pmod 9$.