There always exists a multiple with the specified number of digits

53 Views Asked by At

For any positive natural number $N$, with any number of digits there is a multiple of $N$ with that many digits, as long as it is at least as many as are in $N$.

This is true for any base (binary, terenary, decimal, hexadecimal, etc).

For example, there is a multiple of $37$ with $7$ digits : $1,850,000 = 37 \times 50,000$.

I came across this problem writing some software. I needed it to be true to prove the correctness of an arithmetic program.

I managed to prove/disprove it, thought someone else might enjoy trying.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose, for a contradiction, that there are no $k$-digit multiples of an $n$-digit integer $N$, in base $b$, for $n\leq k$. Since one out of every $N$ consecutive integers must be a multiple of $N$, this implies $$b^k-b^{k-1}<N\Rightarrow$$ $$(b-1)\cdot b^{k-1}<N.$$ However, by hypothesis, $N<b^{n-1}$. This is only possible if $n=k$. But in that case, $N$ is a $k$-digit multiple of $N$, and we’ve arrived at our contradiction. $\blacksquare$