Monday, September 7, 2015

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



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.


Answer



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}$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...