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