How many 5-digit numbers such that the sum of their digits is a multiple of 4? My textbook has the same problem, except for 5-digit numbers the sum of whose digits is a multiple of 5. The general approach is:
Select the first 4 digits. Number of possible ways of doing this = $9\times 10 \times 10 \times 10$ since the ten thousands-place digit cannot be zero. The sum of these 4 digits is $5k$, $5k+1$, $5k+2$, $5k+3$, or $5k+4$. If it's $5k$, the last digit may only be $0$ or $5$. Sum is $5k+1 \implies$ last digit is $4$ or $9$, and so on. In each case, there are only $2$ possible last digits.
Therefore the total number of such 5-digit numbers is $9\times 10 \times 10 \times 10 \times 2 = 18000$.

When we apply this approach to the "sum of digits is a multiple of 4" problem, we get,
Sum of first 4 digits is $4k \implies$ last digit is $0$, $4$, or $8$.
Sum of first 4 digits is $4k+1 \implies$ last digit is $3$ or $7$.
Sum of first 4 digits is $4k+2 \implies$ last digit is $2$ or $6$.
Sum of first 4 digits is $4k+3 \implies$ last digit is $1$, $5$ or $9$.
In two of these cases, we get three possible last digits and in the other two, we get two possible last digits. Our general approach clearly breaks down here. One way to go around this would be to ask ourselves, "how many ways can we select four digits such their sum is $4k$ or $4k+3$", and multiply that number by 3; repeat for $4k+2$ and $4k+1$ but multiply by 2. Add both these numbers to get the answer.
This seems too long. Is there a simpler way to do this?
 A: Let $S$ be the set of numbers where at least one digit is in the range $\{1,\dots,8\}$. I claim that exactly one fourth of the numbers in $S$ have a digit sum which is a multiple of $4$. To do this, we will partition $S$ into groups of four, where the numbers in each group have different remainders modulo $4$.

*

*Let $S_1$ be the set of numbers in $S$ whose first digit is in $\{1,\dots,8\}$, and let $x$ be some number in $S_1$. If the first digit of  $x$ is in $\{1,2,3,4\}$, the group containing $x$ is made by changing that digit to the other numbers in $\{1,2,3,4\}$. For example, the group containing $34682$ would be $\{14682, 24682, 34682, 44682\}$. You do the corresponding thing if the first digit is in $\{5,6,7,8\}$.


*But what do we do if the first digit is $0$ or $9$? You then consider $S_2$, the set of numbers whose first digit is $0$ or $9$, and whose second digit is in $\{1,\dots,8\}$, and do the same procedure in the first bullet to the second digit.


*Then, you let $S_3$ be the set of numbers each of whose first two digits are $0$ or $9$, and whose third digit is in $\{1,\dots,8\}$, and do the same thing. Same with $S_4$.
Since $S$ is the non-overlapping union of $S_1,S_2,S_3$ and $S_4$, we have partitioned $S$ into groups of four as desired. Therefore, we need to count the number of numbers in $S$ and divide by $4$ to find the number of desired numbers in $S$. To count $S$, use complementary counting.
What about the numbers outside $S$? There are only $16$ of these, and you can count the number of these whose digit sum is a multiple of four directly.
A: Denote by $a_i(n)$ $\>(0\leq i\leq3)$ the number of $n$-digit decimal strings having a digit sum leaving remainder $i$ modulo $4$, and collect the $a_i(n)$ into $a(n):=\bigl(a_0(n), a_1(n), a_2(n), a_3(n)\bigr)$, the latter considered as a column vector. We then have $$a(1)=(2,3,2,2)\ .$$ For the latter digits the multiplicities of the possible remainders are $(3,3,2,2)$, since the digit ${\tt 0}$ with remainder $0$ is allowed.
What we have written already allows to compute $$a_0(2)=3\cdot2+2\cdot3+2\cdot2+3\cdot2=22\ .$$
Indeed, when the first digit has remainder $0$ the second also has to have remainder $0$, and when the first digit has remainder $1$ the second has to have remainder $3$, etcetera. This idea, used for all possible remainders, leads to the recursion
$$ a(n+1)=A\ a(n)\qquad(n\geq1),\qquad A:=\left[\matrix{3&2&2&3\cr3&3&2&2\cr2&3&3&2\cr2&2&3&3\cr}\right]\ .$$
In this way we obtain
$$a(5)=A^4\ a(1)=\bigl(22500, 22498, 22500, 22502\bigr)\ ,$$
so that the number we are looking for is $22\,500$. In order to compute, e.g., $a(23)$ we better find a scheme for computing the higher powers of the "cyclic" matrix $A$.
