Difference between revisions of "2014 UNM-PNM Statewide High School Mathematics Contest II Problems/Problem 5"
(→Solution) |
(→Solution) |
||
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
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 , what is this digit?
Solution
Lemma: The sum of the digits of are congruent to .
Let represent the sum of the digits of . We can prove that by expressing in the form , where s are digits in the decimal expansion of . By using the fact that for all , we get
Therefore .
Since we repeatedly compute the sum of the digits of , the value of each term will be congruent to . Therefore, we only need to find such that . Using Euler's formula, we know that . Therefore,
So our answer is .
- 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 |