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)
 
(2 intermediate revisions by 2 users not shown)
Line 6: Line 6:
  
 
== 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.
+
 
−
Any number can be represented in base-10 like this:
+
Lemma: The sum of the digits of <math>n</math> are congruent to <math>n \pmod 9</math>.
−
<cmath>N=a_{1}\cdot10^n+a_{2}\cdot10^{n-1}+\cdots+a_{n-1}\cdot10^1+a_n,</cmath>
+
 
−
where <math>0<a_n<10</math>. Now realize <math>10\equiv1 \pmod{9}</math>, so you can use properties of mod to find <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 \equiv a_1+a_2+\cdots+a_{n-1}+a_n \pmod{9}</cmath>
+
 
−
What is significant here? By repeatedly summing the digits, you are repeatedly looking for the remainder when that sum is divided by 9. This means that the answer will be the original number <math>\pmod{9}</math>. Either by using the Euler Theorem and the fact that <math>\phi(9)=6</math>, or just by finding a pattern, you see that <math>5^6 \equiv 1 \pmod{9}</math>. This means that <math>5^{2014}=(5^6)^{335}\cdot 5^4 \equiv 5^4 \pmod{9}</math>, which, if calculated properly (not that hard to do), gives you a digit of <math>\boxed{4}</math>.
+
<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 ==
 
{{UNM-PNM Math Contest box|year=2014|n=II|num-b=4|num-a=6}}
 
{{UNM-PNM Math Contest box|year=2014|n=II|num-b=4|num-a=6}}
  
−
[[Category:Intermediate Number Theory Problems]]
+
[[Category:Intermediate Algebra Problems]]

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"