1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.