Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution)
(→‎Solution)
 
Line 6: Line 6:
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
 
−
What you have to realize is that the sum of the digits of a number is the number <math>\pmod{9}</math>. We can prove this right now.
+
Lemma: The sum of the digits of <math>n</math> are congruent to <math>n \pmod 9</math>.
−
\begin{equation}
+
 
−
\end{equation}
+
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 (Problems • Answer Key • Resources)
Preceded by
Problem 4 		Followed by
Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10
All UNM-PNM Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_UNM-PNM_Statewide_High_School_Mathematics_Contest_II_Problems/Problem_5&oldid=166960"