# 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?

• Consider the set $S$ of numbers where at least one of the digits is in the 1-8 range. You can show that exactly one fourth of the numbers in $S$ have a digit sum which is a multiple of four. Once you prove this, all that remains is to count the number of numbers outside $S$ whose digit sum is a multiple of four, which is easy (these numbers only have the digits 0 and 9). Nov 16, 2020 at 17:01
• @MikeEarnest but how would you prove your first lemma? Nov 17, 2020 at 2:41
• @AlbusDumbledore The first Lemma is immediate for much the same reason as the OP used when considering sum of digits mod 5. Regardless of the sum of digits mod 4 of all but the rightmost digit, there will always be exactly two of the rightmost digits (out of the 8 digits 1,2,...,8) that result in a sum that is a multiple of 4. Nov 17, 2020 at 6:45
• @MikeEarnest Very elegant. I request that you transplant your analysis into an answer, also showing how to deal with the numbers that end in either 0 or 9. Nov 17, 2020 at 6:49
• Does this answer your question? 5 digits numbers such that when the sum of digits divided by 4 leaves remainder 2. The question asks for digit sums equal to 2 modulo 4, but my answer (which is very similar to the comment from @MikeEarnest) gives the number for all residue classes. (The answer is $22500$.) Nov 17, 2020 at 16:56

## 2 Answers

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.

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