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

227 Views Asked by At

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

There are 1 best solutions below

0
On BEST 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$.