Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If A is the sum of the digits of $5^{10000}$, B is the sum of the digits of A, and C is the sum of the digits of B, what is C? I know it has something to do with mod 9, but I'm not sure how do use it to solve the problem. I found this question in my Math Challenge II Number Theory Packet, and I got confused.

share|improve this question
1  
What's going on with these close votes? The OP clearly showed effort, people. Maybe try reading the question in its entirety. In any case, other than that $C\equiv B\equiv A\equiv5^{10000}\mod9$, I don't see how $\mathbb Z/9\mathbb Z$ is going to help us here, are you sure it's relevant? –  Jack M May 8 at 0:57
    
all I know is that using mod 9 gives the sum of digits mod 9, so I think it might help somehow –  Jason Chen May 8 at 0:58
    
That tells you $A \equiv B \equiv C \mod 9$, and that you can compute $5^{10000} \mod 9$ to figure out the residue class modulo $9$. Then there's probably a counting argument you can do to show that $C$ must be a $1$ digit number, and is therefore determined. I could be wrong though. –  Dustan Levenstein May 8 at 1:03
1  
An important point is that sum of digits is about $4.5$ times the base $10$ log, so it shrinks big numbers quickly –  Ross Millikan May 8 at 1:18

2 Answers 2

up vote 9 down vote accepted

Clearly $5^{10000}$ is a number with fewer than $10000$ digits, and the sum of these digits is less than $90000$. That is, $A<90000$. So $A$ has at most $5$ digits and the same argument shows that $B\le45$. The largest sum of digits of any number less than $45$ is $12$ (if the number is $39$), so $C\le12$. But $C$ must be the same as the original number modulo $9$ and so $$C\equiv5^{10000}\equiv5\times(5^3)^{3333}\equiv5\times125^{3333} \equiv5\times(-1)^{3333}\equiv-5\pmod9\ .$$ The only positive integer less than or equal to $12$ which is congruent to $-5$ modulo $9$ is $4$, and this is the value of $C$.

share|improve this answer
    
$B\le44$ because the value of $A$ with the largest sum of digits is $89999$. –  Jason Chen May 14 at 4:26
1  
@JasonChen that's true. If you want to do this kind of thing you could also say that $\log_{10}(5^{10000})<6990$, so $5^{10000}$ has at most $6990$ digits, and the last two digits are $25$, so $A\le62899$, so $B\le41$. However this merely adds extra work without improving the solution. The point is that the most trivial, mindless estimates are still enough to solve the problem. –  David May 14 at 6:25
    
And $B\le 44$ would simply be a stronger argument. The statement $B\le 45$ is not false. There's no necessity of $a$ being equal to $b$ when $a\le b$. –  mathh May 18 at 15:44
    
@mathh It would not be a stronger argument, it would be an equally strong but (slightly) more difficult argument. It is elegant to obtain the required result with minimum work. –  David May 18 at 21:37
    
@David Why not? How do you understand the word 'stronger'? What I meant was that the inequality is sharper. We have better information about $B$ if we know that $B\le 44$ instead of $B\le 45$ because of the fact that $B$ cannot be equal to $45$. And I didn't imply that it is useful in this case. I only informed Jason that the argument $B\le 45$ in intself is not false in case he didn't know but he likely did though. –  mathh May 20 at 4:08

Let $S(n)$ denote the sum of digits of $n$. Then, note that $S(n) \le 9(\lfloor\log_{10}(n)\rfloor + 1)$.

Thus,

$(S(5^{10000}) \le 9(\lfloor\log_{10}(5^{10000})\rfloor + 1) = 9(\lfloor10000\log_{10}(5)\rfloor + 1) = 9(\lfloor1000\log_{10}(5^{10})\rfloor + 1) = 9(\lfloor1000\log_{10}(9765625)\rfloor + 1) \le 9(\lfloor1000\log_{10}(10000000)\rfloor + 1) = 9(\lfloor1000\log_{10}(10^7)\rfloor + 1) = 9(\lfloor1000(7)\rfloor + 1) = 9(7001) = 63009$

Also note that the maximum possible sum of digits of the numbers $\le 63009$ is $59999$, with sum of digits $41$. Now, the number with the maximum sum of digits that is $\le 41$ is $39$, with sum of digits $12$. So, $C \le 12$.

Since $5^{10000} \equiv (5^2)^{5000} \equiv 25^{5000} \equiv (-2)^{5000} \equiv 2^{5000} \equiv (2^3)^{1666} \cdot 4 \equiv 8^{1666} \cdot 4 \equiv (-1)^{1666} \cdot 4 \equiv 4 \pmod{9}$.

Since $C \equiv 5^{10000} \pmod{9}$ and $0 \le C \le 12$, $C = 4$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.