2014 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 5

Problem

$5^n$ is written on the blackboard. The sum of its digits is calculated. Then the sum of the digits of the result is calculated and so on until we have a single digit. If $n = 2014$, what is this digit?

Solution

Lemma: The sum of the digits of $n$ are congruent to $n \pmod 9$.

Let $S(n)$ represent the sum of the digits of $n$. We can prove that $S(n) \equiv n \mod 9$ by expressing $n$ in the form $\overline{a_k a_{k-1} \cdots a_1 a_0}$, where $a_i$s are digits in the decimal expansion of $n$. By using the fact that $9|10^n - 1$ for all $n$, we get

\[n = a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + \cdots + a_1 \cdot 10^1 + a_0 \cdot 10^0 \equiv a_n + a_{n-1} + \cdots + a_1 + a_0 = s(n) \pmod 9\]

Therefore $S(n) = n \pmod 9$.

Since we repeatedly compute the sum of the digits of $n$, the value of each term will be congruent to $n \pmod 9$. Therefore, we only need to find $1 \leq k \leq 9$ such that $k \equiv 5^{2014} \pmod 9$. Using Euler's formula, we know that $5^{\phi(9)} = 5^6 \equiv 1 \pmod 9$. Therefore,

\[5^{2014} = 5^{2010} \cdot 5^4 = (5^6)^{335} \cdot 5^4 \equiv 5^4 = 625 \equiv 4 \pmod 9\]

So our answer is $\boxed{4}$.

- mako17

See also

2014 UNM-PNM Contest II (ProblemsAnswer KeyResources)
Preceded by
Problem 4
Followed by
Problem 6
1 2 3 4 5 6 7 8 9 10
All UNM-PNM Problems and Solutions