Positional notation: proof of relations for different base but same digits

74 Views Asked by At

I have the following situation:

Be $n_1, n_2, b_1, b_2 \in \mathbb{N}$ with the notation of $n_1$ in base $b_1$ and $n_2$ in $b_2$ and the digits $z_{l-1}z_{l-2}...z_0$

Furthermore, be $b_1 > b_2$ and $m \in \mathbb{N}$

Proof (or refute) that there exists an $N \in \mathbb{N}$ so that if $l > N$ and $z_{l-1} \neq 0$, then $n_1 > mn_2$.

I think that this implication is correct but I struggle with how to proof it. Does anyone have a tip how to go about this?

1

There are 1 best solutions below

3
On BEST ANSWER

For a $l$-digit number $n$ in base $b$, we have the following limits: $(\underbrace{100\ldots 0}_l)_b\le n\lt (\underbrace{100\ldots 0}_{l+1})_b$, i.e. $b^{l-1}\le n \lt b^l$.

Now, if we can have $mb_2^l\le b_1^{l-1}$ for a sufficiently large $l$, then, for any $l$-digit number $n_1$ in $b_1$ and any $l$-digit number $n_2$ in $b_2$ we will have:

$$mn_2<mb_2^l\le b_1^{l-1}\le n_1$$

All that is left is to prove that $mb_2^l\le b_1^{l-1}$ is achievable for sufficiently large $l$. However, this inequality is equivalent with $mb_1\le\left(\frac{b_1}{b_2}\right)^l$, and this is certainly true for "large enough" $l$ because $b_1>b_2$, and so we have that the right-hand side diverges to $+\infty$ (when $l\to\infty$), while the left-hand side is a constant. More explicitly, you may take $l\ge N=\lceil\log_{b_1/b_2}(mb_1)\rceil$.

(Note we have proven the inequality not only in the case $n_1$ and $n_2$ have the same digits, but in the case of them having arbitrary digits, as long as both are with the same number of digits and the leading digit is nonzero in both.)