# Increasing the number of nonzero digits (from AOPS)

I found this currently unsolved problem in the AOPS site (link):

Let $n$ be a positive integer with exactly $d$ non-zero digits. Show that there is a multiple of $n$ which has exactly $d+1$ non-zero digits.

It seems to be quite challenging and I have no idea how to solve it. Any hints how to proceed?

• Interesting problem! Could be out of reach. – Peter Aug 8 '18 at 22:35
• How many digits does $n$ have? Is it $d$ or more? – user582949 Aug 10 '18 at 18:45
• @user582949 $n$ can have more than $d$ digits: $d$ are nonzero and the others are zero. – Frank S Aug 10 '18 at 20:36

You can combine three simple tricks to solve the problem:

1. Take a digit greater than $1$, and split it into two nonzero digits by adding $10^t-10^s$.

2. If each digit in your number $n$ is $0$ or $1$, replace $n$ by $2n$.

3. In order to get rid of the prime factors $2$ and $5$, multiply $n$ by a power of $10$.

If $n$ has a digit greater than $1$ then let $m=n$. Otherwise, if each digit of $n$ are $0$ or $1$ then let $m=2n$. Hence $m$ is a multiple of $n$, it has the same nonzero digits as $n$, and $m$ has at least one digit grater than $1$.

Let $m=\sum_{i=0}^{k-1} a_i\cdot 10^i$ where $a_0,\ldots,a_{k-1}$ are the decimal digits of $m$ and let $g$ be an index with $a_g\ge2$.

Take two integers $t,s$ such that $s>g$, $t>s+k$ and $10^t\equiv 10^s\pmod{n}$, and choose $$M = 10^{s-g}m + (10^t-10^s).$$ The factor $10^{s-g}$ shifts the digit $a_g$ to the $s$th position. The term $10^t-10^s$ replaces the digit $a_g$ by $a_g-1$ (which is nonzero), and adds a new leading digit $1$. Due to $t-s>k$, this leading $1$ is not added to the previous nonzero digits.

• I have a few questions, but perhaps the most significant is this: Is there a guarantee that we can always choose such $s,t$ so that $10^s\equiv 10^t \pmod n$? – Allawonder Aug 15 '18 at 19:11
• @Allawonder By the pigeonhole principle, in the infinite sequence $\{10^n\}_n$ there are infinite couples $(10^s,10^t)$ with $s\not=t$ such that $10^s$ and $10^t$ have the same remainder when divided by $n$. – Robert Z Aug 15 '18 at 20:13
• @RobertZ Thanks for your response, but I cannot say I understand your argument. Could you be more explicit as to how the pigeonhole principle does what we want? On the other hand the number $10^s-10^t$ is always of the form $\underbrace{999...99}_{s-t \,\,\,9's}\underbrace{00...0}_{t\,\,\, 0's}.$ How does this help us out? I mean, apart from the fact that it is not obvious that every prime divides a number of this form, how does it help to increase the digit by just one in every case? I don't know if I'm making any sense. – Allawonder Aug 19 '18 at 18:22
• @Allawonder Note that $M = 10^t +10^{s-g}m -10^s$: $10^t$ increases the number of non-zero digits and $10^{s-g}m -10^s$ decreases by one the digit at $s$-position (which is at least $2$). – Robert Z Aug 20 '18 at 7:10
• @RobertZ I think I'm beginning to get the gist now. I pay attention to notation, and the parentheses around $10^t-10^s$ may have misled me into thinking of it as $10^s(10^{t-s}-1).$ – Allawonder Aug 20 '18 at 7:45