The number of digits in the bijective base-k numeral for n is ⌈logk((n+1)(k−1))⌉(k≥2, n≥0). Why?

Question

Brian Scott provides a proof (Brian M. Scott (https://math.stackexchange.com/users/12042/brian-m-scott), How many digits are in the bijective base-k numeral for n?, URL (version: 2013-12-16): https://math.stackexchange.com/q/608884)

I understand everything except the leap here: "These are precisely the multiples (k - 1)m of (k - 1) that satisfy k^l ..." Why does (k - 1)m enter the picture and how do I know that (k - 1)m = (k - 1)(n + 1)?

I would add this as a comment to the original answer, but I don't have enough reputation points to do so.

Answer 1

The relevant passage in full:

However, taking advantage of the fact that $n$ is an integer, we can also observe that as $n$ runs over the set $$\left\{\frac{k^\ell-1}{k-1},\ldots,\frac{k^{\ell+1}-1}{k-1}-1\right\}$$ of integers of length $\ell$, $(k-1)n$ runs over the set of multiples of $k-1$ between $k^\ell-1$ and $k^{\ell+1}-k$ inclusive, and therefore $(k-1)(n+1)$ runs over the set of multiples of $k-1$ between $k^\ell+k-2$ and $k^{\ell+1}-1$ inclusive. These are precisely the multiples $(k-1)m$ of $k-1$ that satisfy $k^\ell\le(k-1)m<k^{\ell+1}$ ...

The claim in question is that the set of multiples of $k-1$ between $k^\ell+k-2$ and $k^{\ell+1}-1$ inclusive is equal to the set of multiples $(k-1)m$ of $k-1$ such that

$$k^\ell\le(k-1)m<k^{\ell+1}\;.$$

We know that $k^\ell-1$ is a multiple of $k-1$; say $k^\ell-1=(k-1)m_0$. Similarly,

$$k^{\ell+1}-1=(k-1)m_1$$

for some integer $m_1$. Then

$$k^\ell+k-2=(k-1)(m_0+1)\;,$$

so the set of multiples of $k-1$ between $k^\ell+k-2$ and $k^{\ell+1}-1$ inclusive is the set of multiples $(k-1)m$ of $k-1$ such that $m_0+1\le m\le m_1$: it’s the set

$$M=\{(k-1)m:m_0+1\le m\le m_1\}\;.$$

Now $(k-1)m_0=k^\ell-1<k^\ell$, but

$$(k-1)(m_0+1)=(k^\ell-1)+(k-1)=x^\ell+k-2\ge k^\ell\;,$$

since $k\ge 2$, so $m_0+1$ is the smallest $m$ such that $k^\ell\le(k-1)m$. This means that $m_0+1\le m$ if and only if $k^\ell\le(k-1)m$. And $(k-1)m_1=k^{\ell+1}-1$, so $m_1$ is clearly the largest $m$ such that $(k-1)m<k^{\ell+1}$, meaning that $m\le m_1$ if and only if $(k-1)m<k^{\ell+1}$.

Thus, $m_0+1\le m\le m_1$ if and only if $k^\ell\le(k-1)m<k^{\ell+1}$, and therefore $M$ is just the set of multiples $(k-1)m$ of $k-1$ such that $k^\ell\le(k-1)m<k^{\ell+1}$.