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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Jack M May 8 '14 at 0:57
  • $\begingroup$ all I know is that using mod 9 gives the sum of digits mod 9, so I think it might help somehow $\endgroup$ – Jason Chen May 8 '14 at 0:58
  • $\begingroup$ 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. $\endgroup$ – Dustan Levenstein May 8 '14 at 1:03
  • 1
    $\begingroup$ An important point is that sum of digits is about $4.5$ times the base $10$ log, so it shrinks big numbers quickly $\endgroup$ – 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$.

  • $\begingroup$ $B\le44$ because the value of $A$ with the largest sum of digits is $89999$. $\endgroup$ – Jason Chen May 14 '14 at 4:26
  • 1
    $\begingroup$ @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. $\endgroup$ – David May 14 '14 at 6:25
  • $\begingroup$ 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$. $\endgroup$ – user26486 May 18 '14 at 15:44
  • $\begingroup$ @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. $\endgroup$ – David May 18 '14 at 21:37
  • $\begingroup$ @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. $\endgroup$ – 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)$.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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