Difference between revisions of "2014 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 5"

(Created page with "== Problem == <math>5^n</math> 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 ...")
 
(Solution)
 
(5 intermediate revisions by 3 users not shown)
Line 6: Line 6:
  
 
== Solution ==
 
== Solution ==
 +
 +
Lemma: The sum of the digits of <math>n</math> are congruent to <math>n \pmod 9</math>.
 +
 +
Let <math>S(n)</math> represent the sum of the digits of <math>n</math>. We can prove that <math>S(n) \equiv n \mod 9</math> by expressing <math>n</math> in the form <math>\overline{a_k a_{k-1} \cdots a_1 a_0}</math>, where <math>a_i</math>s are digits in the decimal expansion of <math>n</math>. By using the fact that <math>9|10^n - 1</math> for all <math>n</math>, we get
 +
 +
<cmath>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</cmath>
 +
 +
Therefore <math>S(n) = n \pmod 9</math>.
 +
 +
Since we repeatedly compute the sum of the digits of <math>n</math>, the value of each term will be congruent to <math>n \pmod 9</math>. Therefore, we only need to find <math>1 \leq k \leq 9</math> such that <math>k \equiv 5^{2014} \pmod 9</math>. Using Euler's formula, we know that <math>5^{\phi(9)} = 5^6 \equiv 1 \pmod 9</math>. Therefore,
 +
 +
<cmath>5^{2014} = 5^{2010} \cdot 5^4 = (5^6)^{335} \cdot 5^4 \equiv 5^4 = 625 \equiv 4 \pmod 9</cmath>
 +
 +
So our answer is <math>\boxed{4}</math>.
 +
 +
- mako17
  
 
== See also ==
 
== See also ==

Latest revision as of 00:06, 29 November 2021

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