How many 4 digit numbers are divisible by 29 such that their digit sum is also 29?

Question

How many $4$ digit numbers are divisible by $29$ such that their digit sum is also $29$?

Well, answer is $5$ but what is the working and how did they get it?

Answer 1

Let the digits be$b,c,d,29-b-c-d$

As $0\le b,c,d\le9,0<b+c+d\le27<29$

Now, $$(29-b-c-d)+10b+100c+1000d=29+9b+99c+999d\equiv-20b+12c-16d$$

We need $29\mid(5b-3c+4d)\equiv-24b-3c+33d\iff29\mid(c+8b-11d)$

For $29\mid(8b-11d)\implies8b-11d=(29k-c)(11\cdot3-8\cdot4)$

$\iff8(b+116k-4c)=11(87k+d-3c)\iff b+116k=11m+4c$

$\iff b\equiv5k+4c\pmod{11}$ and $d\equiv3c+k\pmod{11}$

Test for $c;0\le c\le9$ ensuring $0\le b,c,d\le9$ and $b+c+d\ge20$

Answer 2

Here is a full solution of the problem:

Let $$(a,b,c,29-a-b-c)$$ be the decimal representation of such a number, and write $\equiv$ for equivalence modulo the prime $29$. We want $999a+99b+9c\equiv0$, or $$13 a+12b+9c\equiv0\ .\tag{1}$$ Put $4b+3c=:r$. Then $(1)$ implies $13a+3r\equiv0$, which is satisfied by $a=2$, $r=1$, hence enforces $$a\equiv2r\equiv 8b+6c\ .\tag{2}$$ We now have to determine the solutions of $(2)$ that in addition satisfy the constraints $$a\in[1\>..\>9],\quad b,c\in[0\>..\>9],\quad 20\leq a+b+c\leq27\ .\tag{3}$$ This implies $b+c\geq11$, hence $b\geq2$, so that we can conclude that $$70\leq 8b+6c\leq 126\ .$$ There are only the multiples $3\cdot29=87$ and $4\cdot 29=116$ near this range. In view of $(2)$ we therefore have to find the pairs $(b,c)$ with $$88\leq 8b+6c\leq 96, \quad{\rm resp.,}\quad 118\leq 8b+6c\leq124\tag{4}$$ that lead to an $a$ such that the last constraint $(3)$ is satisfied. The first of the ranges $(4)$ contains the pairs $$(9,4), \ (9,3), \ (8,5), \ (8,4), \ (7,6), \ (6,8), \ (6,7), \ (5,9), \ (5,8)\ ,$$ and the second range contains the pairs $$(9,8), \ (8,9)\ .$$ For each of these pairs $(b,c)$ we now compute $a$ by means of $(2)$, and retain the triples $(a,b,c)$ for which the last condition $(3)$ is satisfied. These are the triples $$(9,9,4), \ (7,8,5), \ (9,6,8), \ (7,5,9), \ (4,9,8)\ .$$ From these triples we then obtain the five numbers $$9947, \ 7859, \ 9686, \ 7598, \ 4988$$ fulfilling the given conditions.