All About 9

Let $n$ be any positive integer where $n < 1000$ . Since $n$ can be expressed using 3 digits, we let the first digit be $a$ , the second be $b$ , and the third be $c$ . This includes the possibility of leading zeros. Note that the condition of $n$ being a multiple of 9 is equivalent to $100a + 10b + c \equiv 0 \pmod{9}$ . Since $100 \equiv 1 \pmod{9}$ and $10 \equiv 1 \pmod{9}$ , the previous congruence implies $a + b + c \equiv 0 \pmod{9}$ (we could also have reached this via the divisibility rule for 9). What we are looking for are $n$ which satisfy precisely two conditions: $\begin{aligned} a + b + c & \equiv 0 \pmod{9} \\ a^2 + b^2 + c^2 & \equiv 0 \pmod{9} \end{aligned}$ The strategy will be to identify in which cases $n$ satisfies the second condition, and then out of those, see when the first condition is also satisfied. We start by examining the squares of digits modulo 9: $\begin{aligned} 0^2 & \equiv 9^2 \equiv 3^2 \equiv 6^2 \equiv 0 \pmod{9} \\ 1^2 & \equiv 8^2 \equiv 1 \pmod{9} \\ 2^2 & \equiv 7^2 \equiv 4 \pmod{9} \\ 4^2 & \equiv 5^2 \equiv 7 \pmod{9} \end{aligned}$ This shows that the only possible residues (modulo 9) of squared digits (and in fact any squared integers) are $Q = \{0,1,4,7\}$ . Since we require $a^2 + b^2 + c^2 \equiv 0 \pmod{9}$ , we look for ways to take three assignments of $a^2,b^2,c^2$ to elements of $Q$ (with replacement) such that the three numbers sum to a multiple of 9. This can be worked out by hand, and there are exactly four ways to do this (up to the order of the summands):

1. $a^2 \equiv b^2 \equiv c^2 \equiv 0 \pmod{9}$ .
2. Exactly two of $a^2,b^2,c^2$ are congruent to 1, while the other is congruent to 7 (modulo 9).
3. Exactly two of $a^2,b^2,c^2$ are congruent to 4, while the other is congruent to 1 (modulo 9).
4. Exactly two of $a^2,b^2,c^2$ are congruent to 7, while the other is congruent to 4 (modulo 9).

Finally, we go through each of these four cases and find choices of $a,b,c$ which also satisfy $a + b + c \equiv 0 \pmod{9}$ :

1. Suppose we have case 1. Then, each of $a,b,c$ are one of 0, 3, 6 and 9. We see that we cannot have an even number of 3's or an even number of 6's, as the resulting digit sum would not be a multiple of 9. Also, we cannot have exactly one 3 and no 6 or exactly one 6 and no 3. All remaining possibilities are satisfactory, and we classify them using the following three subcases:

   • All three digits are 0 or 9. Then, we see that any combination of assignments of $a,b,c$ to 0 and 9 will give a multiple of 9, so we have $2^3 = 8$ possibilities in this subcase (since we have 2 choices for each of three digits). However, $n$ must be positive, so we discard the possibility of $n = 000$ and we end up with 7 possibilities.
   • All three digits are 3 or all three digits are 6. These are both satisfactory subcases, as $3 + 3 + 3 = 9$ and $6 + 6 + 6 = 18$ are both multiples of 9.
   • There is exactly one 3 and one 6, and the remaining digit is one of 0 and 9. We see that any assignment within this case satisfies both conditions, since $3 + 6 + 0 = 9$ and $3 + 6 + 9 = 18$ are both multiples of 9. There are $\binom{3}{2} = 3$ ways to choose the two digits which are 3 and 6, and 2 possible orders of these two digits. There are also 2 choices for the remaining third digit, so we have a total of $3 \cdot 2 \cdot 2 = 12$ choices in this subcase.

   Thus, in this case, we have $7 + 2 + 12 = 21$ total possibilities.

2. Suppose we have case 2. Then, two of the digits are 1 or 8, and the remaining digit is 4 or 5. We examine the three distinct possibilities (up to the order of the digits) of assigning the two digits which are 1 or 8.

   • Suppose both digits are 1. Then, the total digit sum becomes either $1 + 1 + 4 = 6$ or $1 + 1 + 5 = 7$ , neither of which are multiples of 9. Thus, this yields no solutions.
   • Suppose both digits are 8. Then, the total digit sum becomes either $8 + 8 + 4 = 20$ or $8 + 8 + 5 = 21$ , neither of which are multiples of 9. Thus, this yields no solutions.
   • Suppose one is 1 and the other is 8. Then, the total digit sum becomes either $1 + 8 + 4 = 13$ or $1 + 8 + 5 = 14$ , neither of which are multiples of 9. Thus, this yields no solutions.

   Therefore, we conclude that case 2 yields no solutions.

3. Suppose we have case 3. Then, two of the digits are 2 or 7, and the remaining digit is 1 or 8. Just as in case 2, we examine the three distinct possibilities of assigning the two digits which are 1 or 8. We check, by the exact same type of analysis, that there are no solutions for this case.

4. Suppose we have case 4. Then, two of the digits are 4 or 5, and the remaining digit is 2 or 7. As before, we examine the three distinct possibilities of assigning the two digits which are 4 or 5. We check, by the exact same type of analysis, that there are no solutions for this case.

Therefore, the only possibilities are the $\boxed{21}$ from case 1.