# Determine a property of $S_b(n)$, which is the sum of the digits of $n$ when $n$ is expressed in base $b$

The original question Let $$S_b(n)$$ be the sum of the digits of $$n$$ when $$n$$ is expressed in base $$b$$. was asked by Anson Chan on Jan. 24, 2019. Since it was deemed to not have enough context, it was closed & deleted. As I thought it was an interesting question (& had provided the only answer), I unsuccessfully tried to reopen it. I am presenting an adjusted version of it here, along with my updated answer.

For a fixed integer $$b \ge 2$$ and for any positive integer $$n$$, let $$S_b(n)$$ be the sum of the digits of $$n$$ when expressed in base $$b$$. For example, $$S_4(26) = S_4(1 \cdot 4^2 + 2 \cdot 4 + 2 \cdot 1) = 1 + 2 + 2 = 5$$.

Determine all positive integers $$m$$ with the property that for all $$n$$, whenever $$m$$ is a factor of $$S_b(n)$$, them $$m$$ is also a factor of $$S_b(n + 1) - 1$$.

This indicates, to me, a property where the remainder of an integer and the sum of its digits are the same. In particular, with base $$10$$, a number, when divided by $$3$$ or $$9$$, has the same remainder as the sum of the digits. This occurs due to $$3$$ and $$9$$ dividing $$10 - 1 = 9$$. Thus, in general, it seems it will work with any factors of $$b - 1$$ since $$S_b(n + 1) - 1$$ would have the same remainder as $$S_b(n) + 1 - 1 = S_b(n)$$. How do you prove this, plus also find any other cases which may work, or show there are no other such values?

## 1 Answer

Consider any positive integer $$m$$ such that

$$m \mid b - 1 \; \Rightarrow \; b \equiv 1 \pmod m \tag{1}\label{eq1}$$

This gives that

$$b^k \equiv 1 \pmod m \; \; \forall \; k \in \mathbb{N^0} \tag{2}\label{eq2}$$

For any positive integer $$t$$, we have for some sufficiently large non-negative integer $$j$$ that

$$t = \sum_{i = 0}^{j} c_i b^i, \text{ with } \; 0 \le c_i \lt b \; \forall \; 0 \le i \le j \tag{3}\label{eq3}$$

Using \eqref{eq2}, this gives that

$$t \equiv \sum_{i = 0}^{j} c_i \pmod m \tag{4}\label{eq4}$$

However, we also have that

$$S_b\left(t\right) = \sum_{i = 0}^{j} c_i \tag{5}\label{eq5}$$

Putting \eqref{eq4} and \eqref{eq5} together gives that for all positive integers $$t$$ that

$$S_b\left(t\right) \equiv t \pmod m \tag{6}\label{eq6}$$

In regards to the relation to be checked, this means that

$$S_b\left(n + 1\right) - 1 \equiv \left(n + 1\right) - 1 = n \equiv S_b\left(n\right) \pmod m \tag{7}\label{eq7}$$

Thus, if $$m \mid S_b\left(n\right)$$, then $$m \mid S_b\left(n + 1\right) - 1$$.

Next, consider $$m \not\mid b - 1$$. Let $$n$$, in base $$b$$, be $$bm - b + 1$$ digits of $$1$$ followed by a $$0$$ digit and then $$b - 1$$. In this case,

$$S_b\left(n\right) = (bm - b + 1) + (b - 1) = bm \tag{8}\label{eq8}$$

Thus, $$m \mid S_b\left(n\right)$$. However, for $$S_b\left(n + 1\right)$$, the last digit changes to $$0$$ and the second last one increases from $$0$$ to $$1$$, so there is now $$bm - b + 2$$ digits of $$1$$ and $$1$$ digit of $$0$$. This gives

$$S_b\left(n + 1\right) - 1 = (bm - b + 2) - 1 = bm - \left(b - 1\right) \tag{9}\label{eq9}$$

Since $$m \not\mid b - 1$$, this means that $$m \not\mid S_b\left(n + 1\right) - 1$$.

In conclusion, the requested condition is satisfied by a positive integer $$m$$ only if $$m \mid b - 1$$.