Digit sums of a huge power

Idea. Taking digit sums never changes the remainder modulo 9, so the answer has the same remainder as $4444^{4444}$. Size bounds show the answer is small, and only one small number has the right remainder.

Step 1: the remainder. $4444$ has digit sum 16, so $4444\equiv 7(\mathrm{mod}9)$. Since $7^3=343\equiv 1(\mathrm{mod}9)$ and $4444=3\cdot 1481+1$, $$\begin{array}{rl}4444^{4444}& \equiv 7^{4444}=(7^3{)}^{1481}\cdot 7\\ & \equiv 7(\mathrm{mod}9).\end{array}$$ So $A$, $B$ and the answer $C$ are all $\equiv 7(\mathrm{mod}9)$.

Step 2: sizes.

• $4444^{4444}<10^{4\cdot 4444}$, so it has at most 17,776 digits, and $A\le 9\cdot 17,776=159,984$.
• A number at most 159,984 has at most six digits, the first one 0 or 1, so its digit sum is at most $1+5\cdot 9=46$. So $B\le 46$.
• A number at most 46 has digit sum at most $3+9=12$ (for 39). So $C\le 12$.

Step 3. The only number from 1 to 12 that is $\equiv 7(\mathrm{mod}9)$ is 7. So the answer is 7.