# Sum of Digits Question

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.

-
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 '14 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 '14 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 '14 at 1:03
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 '14 at 1:18

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$.

-
$B\le44$ because the value of $A$ with the largest sum of digits is $89999$. –  Jason Chen May 14 '14 at 4:26
@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 '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$. –  user26486 May 18 '14 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 '14 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. –  user26486 May 20 '14 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$.

-