# Sum of digits divisible by $27$

I know that every third number is divisible by $$3$$ and hence, sum of its digits is divisible by $$3$$. Same holds for $$9$$ also. But how do we generalise it? We know that the divisibility condition for higher powers of $$3$$ is not about the sum of digits. How can we find $$n$$ such that in a group of $$n$$ consecutive positive integers, there is a number such that the sum of its digits is divisible by $$27$$ (or $$81,$$ say)? Does it exist? Please prove or disprove.

• Do you understand what makes things work for 3 and 9. Do you have any thoughts about connecting that idea with 27 or 81? Also, since this problem is a bit open ended, it reads like a contest or challenge problem - could you provide the source so we know it's not an active contest/application problem? – Mark S. Jul 27 at 11:37
• math.stackexchange.com/questions/328562/… – lab bhattacharjee Jul 27 at 11:57
• No, I was just thinking about it, related to no contest. I know the idea for $3$ and $9$, we write number as $n_0+10n_1+100n_2+...$ and then take out the sum of the digits, remaining sum turns out to be divisible by $9$, making things easy. – Martund Jul 27 at 11:59
• This is another question by me math.stackexchange.com/questions/3305361/… – Martund Jul 27 at 12:02
• polynomial remainder theorem. – Roddy MacPhee Jul 27 at 12:53

Let $$Q(x)$$ denote the digit sum of $$x$$.

Let $$r\ge 1$$. Then $$n=10^r-1=\underbrace{99\ldots 9}_r$$ is the smallest $$n$$ such that among any $$n$$ consecutive positive integers, at least one has digit sum a multiple of $$9r$$.

That no smaller $$n$$ works, is immediately clear because in $$1,2,3,\ldots, 10^r-2$$, all digit sums are $$>0$$ and $$<9r$$.

Remains to show that in any sequence of $$n$$ consecutive integers, a digit sum divisible by $$9r$$ occurs. This is well-known for $$r=1$$. For $$r>1$$, consider $$n$$ consecutive positive integers $$a,a+1,\ldots, a+n.$$ Among the first $$9\cdot 10^{r-1}=n-(10^{r-1}-1)$$ terms, one is a multiple of $$9\cdot 10^{r-1}$$. Say, $$9\cdot 10^{r-1}\mid a+k=:b$$ with $$0\le k<9\cdot 10^{r-1}$$. Then $$Q(b)$$ is a multiple of $$9$$, and as the lower $$r-1$$ digits of $$b$$ are zero, we have $$Q(b+i)=Q(b)+Q(i)$$ for $$0\le i<10^{r-1}$$ and hence $$Q( b+10^j-1)=Q(b)+9j,\qquad 0\le j\le r-1.$$ (Note that $$k+10^{r-1}-1<10^r-1$$, so these terms are really all in our given sequence). It follows that $$9r$$ divides one of these $$Q(b+10^j-1)$$.

Note that the natural numbers $$\{1,2,\cdots, 999\}$$ contain integers for which the sum of the digits is any specified value $$\pmod {27}$$

Considering the multiples of $$1000$$ we see that each block of $$1000$$ integers contains one which ends in three $$0's$$.

Starting from any integer $$k$$, we go to the next multiple of $$1000$$ (a gap of at most $$999$$). We then add whatever three (or fewer) digit integer we need to "correct" the sum of the digits $$\pmod {27}$$, which takes, at most, another $$999$$.

Thus, every block of $$2\times 999$$ consecutive integers contains at least one for which the sum of the digits is a multiple of $$27$$. A similar argument works for any desired divisor.

I expect the bound could be tightened considerably, but at least this shows that a bound exists.

• Simple insight, great help, thank you:) – Martund Jul 27 at 13:57

Let $$Q(x)$$ denote the digit sum of $$x$$.

$$999$$ is the smallest $$n$$ such that among any $$n$$ consecutive positive integers, at least one has digit sum a multiple of $$27$$.

First note that none of the $$998$$ consecutive integers $$1,2,\ldots ,998$$ has digit sum a multiple of $$27$$.

Any sequence of $$999$$ consecutive integers is either of the form $$\tag11000N+1,\ldots, 1000N+999$$ or $$\tag21000N+k+2,\ldots, 1000N+999,1000(N+1),\ldots, 1000(N+1)+k$$ with $$0\le k\le 997$$.

In $$(1)$$, the digit sums are $$Q(N)+Q(i)$$ with $$i$$ running from $$1$$ to $$999$$ and hence $$Q(i)$$ covering all values from $$1$$ to $$27$$. We conclude that $$(1)$$ contains a term with digit sum a multiple of $$27$$.

So let's look at $$(2)$$: We know $$Q(N+1)\equiv Q(N)+1\pmod 9$$, hence $$Q(N+1)\equiv Q(N)+(1\text{ or }10\text{ or }19)\pmod{27}$$.

• If $$Q(N+1)\equiv 0\pmod{27}$$, then already $$1000(N+1)$$ has the desired property.

• If $$Q(N+1)\equiv 1\pmod {27}$$, then among $$1000(N+1),\ldots, 1000(N+1)+899$$, all remainders $$\bmod27$$ occur, which solves the problem for all $$k\ge 899$$. For $$k\le 898$$, the sequence contains $$1000N+900$$, $$1000N+909$$, and $$1000N+999$$ with digit sums $$Q(N)+9$$, $$Q(N)+18$$, $$Q(N)+27$$. As $$Q(N)\bmod 27$$ is one of $$0$$, $$9$$, $$18$$, we are done.

• More generally, if $$Q(N+1)\equiv r\pmod {27}$$ with $$1\le r\le 9$$, then $$Q(1000(N+1)+999-100r)=Q(N+1)+27-r\equiv 0\pmod{27}$$, which solves the problem for all $$k\ge 999-100r$$. For $$k\le 998-100r$$, the sequence contains $$1000N+(1000-100r)$$, $$1000N+(1009-100r)$$, and $$1000N+(1099-100r)$$ with digit sums $$Q(N)+10-r$$, $$Q(N)+19-r$$, $$Q(N)+28-r$$. As $$Q(N)\bmod 27$$ is one of $$r-1$$, $$r+8$$, $$r+17$$, we are done.

• If $$Q(N+1)\equiv 10+r\pmod{27}$$ with $$0\le r\le 8$$, then $$Q(1000(N+1)+89-10r)=Q(N+1)+17-r\equiv 0\pmod{27}$$, which solves the problem for all $$k\ge 89-10r$$. For $$k\le 89-10r$$, the sequence contains $$1000N+999-r$$, $$1000N+909-r$$, and $$1000N+900-100r$$ with digit sums $$Q(N)+27-r$$, $$Q(N)+18-r$$, $$Q(N)+9-r$$. As $$Q(N)\bmod 27$$ is one of $$r$$, $$r+9$$, $$r+18$$, we are done.

• If $$Q(N+1)\equiv 19+r\pmod{27}$$ with $$0\le r\le 7$$, then $$Q(1000(N+1)+8-r)=Q(N+1)+8-r\equiv 0\pmod{27}$$, which solves the problem for all $$k\ge 8-r$$. For $$k\le 8-r$$, the sequence contains $$1000N+999-r$$, $$1000N+909-r$$, and $$1000N+900-100r$$ with digit sums $$Q(N)+27-r$$, $$Q(N)+18-r$$, $$Q(N)+9-r$$. As $$Q(N)\bmod 27$$ is one of $$r$$, $$r+9$$, $$r+18$$, we are done.

• Great answer, thanks a lot. – Martund Jul 27 at 13:56
• or use polynomial remainder theorem for a rule. – Roddy MacPhee Jul 27 at 14:06

Obviously there are number whose digits add to $$27$$. ($$999$$ or $$524385$$ etc.) and obviously the sum of the digits $$27$$ is a multiple of $$9$$ so they are a multiple of $$9$$ but are they a multiples of $$27$$; and must multiples of $$27$$ have digits adding to a multiple of $$27$$.

Well, $$27$$ itself is an obvious counter example of the latter.

And $$999= 27*37$$ but $$524385= 27*19421\frac 23$$ so the first is not true either.

So the question I guess is why not?

Well the rule works for $$9$$ because $$9 = 10-1$$. And it works for $$3$$ because $$3|9$$.

Details: If $$k|b-1$$ and $$n= \sum_{i=0}^m a_ib^i= \sum_{i=0}^m (a_i)(b^i-1) + \sum_{i=0}^m a_i$$. Now $$b^i-1 =(b-1)(b^{i-1} + b^{i-2}+ ..... + 1)$$ so $$(b-1)$$ divides all of the $$b^i-1$$ so $$b-1$$ divides $$n$$ if and only if $$(b-1)$$ divides $$\sum_{i=0}^m a_i$$. If we let $$b= 10$$ and $$b-1=9$$ and $$a_i$$ be the digits of $$n$$ that's our result.

And it follows that if $$k|b-1$$ then $$k|(b^i-1)$$ so $$k|n$$ if and only if $$k$$ divides $$\sum_{i=0}^m a_i$$ as well.

And this will be true for any decimal system base $$b$$ (not just $$b=10$$ and and $$k|b-1$$ (not just $$3|9$$).

The fact that $$3^2 = 9$$ is mostly a coincidence and powers of $$3$$ is a bit of a red herring. It's not powers of $$3$$ going up that matter, but factors $$10-1$$ going down that matter.

We can note that in base $$7$$ a number is a multiple of $$6$$ if and only if the sum of the digits is a multiple of $$6$$ and a multiple of $$2$$ or of $$3$$ if and only if the sum of the digits is a multiple of $$2$$ or of $$3$$ respectively but nothing can be said of $$4$$ or $$3$$. ($$11_7 = 8$$ is a multiple of $$4$$ but $$1+1=2$$ is not. And $$12_7 =9$$ is a multiple of $$9$$ but $$1+2=3$$ which is not.)

Why doesn't it work? Well. $$27 = 3*(10-1)= (3-1)*10 + (10-3)$$. The sum of the digits of $$27$$ are $$(3-1) + (10-3) = 10-1$$. Our rule of $$9$$s apply and we can't jump magically to $$27$$. And if we increas by $$27$$ if we ignore carrying and borrowing we get $$ab + 27 = (a+2)(b+7)$$ and the sums of the digits are $$a+b + 9$$. That's an increase of $$9$$; not of $$27$$. Ind if we carry (i.e. $$b \ge 3$$ or $$a \ge 8$$ or $$b\ge 3$$ and $$a\ge 7$$) we get the sums are $$(a+2+1)(b+7-10)$$ or $$1(a+2-10)(b+7)$$ or $$1(a+2+1-10)(b+7 - 10)$$ and the sum of the digits stay the same or decreases by $$9$$; not $$27$$.

But if $$b-1 = k^m$$ then in base $$b$$ we will have that multiples of $$k^i; i\le m$$ will have the sum of the digits add to a multiple of $$k^i$$.

Example in base $$28$$ then sum of the digits of a multiple of $$27$$ will add to a multiple of $$27$$.

FWIW $$999_{10} = 28^2 + 7*28 + 19 = 17T_{28}$$ where $$T$$ is the digit for $$19$$.

And $$27*92 = 2484_{10} = 3*28^2+4*28 + 20= 34U_{28}$$ where $$U$$ is the digit for $$20$$ is another example.

Less trivial example. The number $$8ATR_{28}$$ were $$A=10$$ and $$T=19$$ and $$R=17$$ will have digits that add to $$8+10+19+17=54$$, so my claim is that it ought to be a multiple of $$27$$. And

$$8ATR_{28} = 8*28^3 + 10*28^2+ 19*28 + 17 =$$

$$8(27+ 1)^3 + 10(27+1)^2 + 19(27+1) + 17 =$$

$$8(27^3 + 3*27^2+3*27 + 1) + 10(27^2 + 2*27 + 1) + 19(27+1)+17=$$

$$[8*27^3 + 3*27^2 + 3*27 + 20*27^2 + 2*27 + 19*27] + 8 + 10 + 19+17=$$

$$27(8*27^2 + 3*27 + 3 + 20*27 + 2 + 19) + 54 =$$

$$27(8*27^2 + 3*27 + 3 + 20*27 + 2 + 19 + 2)$$ is a multiple of $$27$$.

And indeed $$8*28^3 + 10*28^2+ 19*28 + 17=184005 = 27*6815$$