11
$\begingroup$

Does every number not ending with zero have a multiple without zero digits at all?

We consider numbers in their usual base 10 representation. we don't consider numbers ending with $0$, because all multiples of such numbers end with $0$.

It can be proven that all powers of $2$ have such a multiple: Indeed, for every number of the form $2^n$, we can find a multiple $l$ of it whose last $n$ digits are nonzero (This can be done by repeatedly multiplying a number by $10^k+1$, as explained here), and then forget all other digits; these last $n$ digits constitute a number that is still divisible by $2^n$, since it is obtained from $l$ by subtracting a multiple of $10^n$ which is in particular a multiple of $2^n$.

The same argument shows that every power of $5$ has a multiple without zeros, but this does not seem to generalize to other numbers.

My intuition is actually that the claim is not true, since the density of numbers without any zero digits approaches $0$ for big numbers. This is because the probability of a random number with at most $n$ digits to contain only nonzero digits is $(\frac{9}{10})^n$. Thus big numbers "nearly always" contain a zero. This hints on the existence of a counterexample, but does not prove its existence.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure what the answer is, but I think your heuristic argument misses something big: Sure, the proportion of $n$ digit numbers with only non-zero digits is $(9/10)^n$, but the number of multiples of a number $k$ with $n$ digits is roughly $\frac{10^n}k$ - so multiply those together and we "expect" there to be $\frac{9^n}k$ multiples of $k$ with $n$ digits and no zeros. (This is certainly true of numbers coprime to 10) $\endgroup$ – Milo Brandt Dec 21 '16 at 20:51
  • $\begingroup$ User @lulu seems to have deleted his correct observation that this is also true for all numbers coprime to $10$, by Fermat's little theorem. $\endgroup$ – Emolga Dec 21 '16 at 21:06
  • $\begingroup$ I deleted the post because someone pointed out this question which generalizes the straightforward argument I gave. $\endgroup$ – lulu Dec 21 '16 at 21:08
  • 1
    $\begingroup$ Just a note: in fact you can get stronger results for multiples of $2^n.$ For any odd digit $a$ and even digit $b$ you can find a multiple of $2^n$ using only $a$ and $b$ $\endgroup$ – cats Dec 21 '16 at 21:12
  • 3
    $\begingroup$ Found it - see "104 Number Theory Problems from the training of the USA IMO Team" Introductory Problems #52 $\endgroup$ – cats Dec 21 '16 at 21:18
5
$\begingroup$

Then answer is yes.

If $n$ is relatively prime to $10$ then the answer is easy, see for example this post.

If, $n=2^k m$ with $m$ relatively prime to $10$ or $n=5^km$ with $m$ relatively prime to $10$, then prove first the following by induction:

Claim 1 $2^k$ has a $k$ digits multiple containing only the digits $1$ and $2$.

Claim 2 $5^k$ has a $k$ digits multiple containing only the digits $1,2,3,4$ and $5$.

Both are easy induction exercises.

Once you prove this, proceed as follows (same idea as in the posted link):

$n=2^k m$ or $n=5^km$ with $gcd(m,10)=1$.. Then, we know that $2^k$ respectively $5^k$ has a multiple of the form $\overline{a_1...a_k}$

Look at the following numbers $$\overline{a_1...a_k} , \overline{a_1...a_ka_1...a_k} , \overline{a_1...a_ka_1...a_ka_1...a_k} , ...$$

In this infinite list, there exists two numbers with the same reminder when divided by $m$. Their difference is a multiple of $m$.

Therefore $$m| \overline{a_1...a_ka_1...a_ka_1...a_k00...0}=\overline{a_1...a_ka_1...a_ka_1...a_k}\cdot 10^l$$ Since $m$ is relatively prime to $10$ it follows that $$m|\overline{a_1...a_ka_1...a_ka_1...a_k}$$ Since $2^k$ respectively $5^k$ also divide $\overline{a_1...a_ka_1...a_ka_1...a_k}$, and they are relatively prime to $m$, it follows that $$n|\overline{a_1...a_ka_1...a_ka_1...a_k}$$

P.S. We proved that $n$ has a multiple which can be written only with the digits $1,2,3,4,5$. These digits can be replaced by any $5$ digits which cover all classes $\pmod{2}$ and $\pmod{5}$.

$\endgroup$
  • $\begingroup$ Could you please give a proof of the claims? $\endgroup$ – J. Abraham Feb 25 '17 at 19:56
  • $\begingroup$ @J.Abraham $P(k) \Rightarrow P(k+1)$. Let $A$ be the $k$ digit number which is divisible by $a^k$ where $a=2$ or $5$. Then $$A=a^k \cdot m$$ and $$10^{k}=a^k \cdot l$$ where $l$ is invertible modulo $a$. Then the equation $$x l +m \equiv 0 \pmod{a}$$ has an unique solution in the listed digits. Then $$x \cdot 10^k+A$$ is the desired $k+1$ digit number. $\endgroup$ – N. S. Feb 26 '17 at 23:07

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.