Difference between revisions of "Mock AIME II 2012 Problems/Problem 3"

(Created page with "==Problem== Let <math>\{a_n\}</math> be a recursion defined such that <math>a_1=1, a_2=20</math>, and <math>a_n=\sqrt{\left| a_{n-1}^2-a_{n-2}^2 \right|}</math> where <math>n\ge ...")
 
 
Line 1: Line 1:
 
==Problem==
 
==Problem==
Let <math>\{a_n\}</math> be a recursion defined such that <math>a_1=1, a_2=20</math>, and <math>a_n=\sqrt{\left| a_{n-1}^2-a_{n-2}^2 \right|}</math> where <math>n\ge 3</math>, and <math>n</math> is an integer. If <math>a_m=k</math> for <math>k</math> being a positive integer greater than <math>1</math> and <math>m</math> being a positive integer greater than 2, find the smallest possible value of <math>m+k</math>.
+
The <math>\textit{digital root}</math> 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 <math>\textit{digital root}</math> of <math>237</math> is <math>3</math> (<math>2+3+7=12, 1+2=3</math>). Find the <math>\textit{digital root}</math> of <math>2012^{2012^{2012}}</math>.
  
 
==Solution==
 
==Solution==

Latest revision as of 01:02, 11 July 2012

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$.