9
$\begingroup$

Prove that there exists a number divisible by $5^{1000}$ not containing a single zero in its decimal notation.

The above question is taken from this site. It is question no. 88 in the list. I could not find any solutions for this problem. Apparently a "schoolboy" should be able to solve this question.

In general, I have a hunch that this statement must be true for any number (instead of $5^{1000}$). However, I cannot think of a strategy to show there are no zeros in the decimal expansion. Trailing zeros are trivial to catch but zeros in the middle confound me.

Is there a clever construction for the case of $5^{1000}$?

Edit: As explained in the comments, my hunch does not make sense for a multiple of 10.

$\endgroup$
  • 4
    $\begingroup$ Clearly it is not true for $10$, for example, so it is not true for any integer. $\endgroup$ – Václav Mordvinov May 9 '18 at 5:53
  • $\begingroup$ Looking at the first couple powers of $5$ we find some numbers do contain zeros, so I would expect that there is some way to show that there is always a later power of $5$ that contains no zeros in it's decimal expansion. $\endgroup$ – Benji Altman May 9 '18 at 6:09
  • 1
    $\begingroup$ A number is divisible by $5^{1000}$ if and only if its last $1000$ digits are, therefore we may restrict ourselves to numbers with less than a thousand digits, although that doesn't really help things. I just looked at $5^{1000}$ and it has quite a few zeros and $699$ digits in total, so I think this question is a real crazy one. $\endgroup$ – астон вілла олоф мэллбэрг May 9 '18 at 6:18
  • $\begingroup$ One idea might be this: if $x\mod 10^{i+1} = x\mod 10^i$, then the first number (of those that are left) must be $0$ $\endgroup$ – Sudix May 9 '18 at 6:32
  • $\begingroup$ I have posted an answer. Please have a look. $\endgroup$ – астон вілла олоф мэллбэрг May 9 '18 at 7:02
8
$\begingroup$

Idea of Approach

By induction, an using the fact that $5^{n}$ is a divisor of $10^n$ and $10^{n-1}$ leaves only a certain kind of remainder when divided by $5^n$.

Claim and proof

Claim : For all $n$, there exists an $n$ digit multiple of $5^n$ that does not contain any zeros.

Proof : Start with the base case : $5 , 25 , 125$ for $n = 1,2,3$.

The inductive case : let $L$ be an $n$ digit number that has no non-zero digits and is a multiple of $5^n$. We want a number of the form $a \times 10^{n} + L$(this will have $n+1$ digits) that divides $5^{n+1}$, where $a \neq 0$.

Well, if $a \times 10^n + L$ is a multiple of $5^{n+1}$ then the remainders when you divide $a \times 10^n$ and $L$ by $5^{n+1}$ respectively, must sum up to a multiple of $5^{n+1}$.

But both are multiples of $5^n$, so $10^n$ leaves a remainder of $b 5^n$ when divided by $5^{n+1}$ and $L$ leaves a remainder of $c 5^n$ when divided by $5^{n+1}$.

Hence, $a 10^n + L$ leaves the remainder $(ab+c)5^n$ when divided by $5^{n+1}$.

Note that $b$ cannot be zero since $10^n$ is not a multiple of $5^{n+1}$. But $c = 0$ is possible.

So the question is : can we make $ab+c$ a multiple of $5$ everytime?

If $c = 0$ then take $a = 5$, since in that case, regardless of $b$ we have $ab+c$ is a multiple of $5$.

If $c \neq 0$ then since $b \neq 0$ we take $a = (-c)b^{-1} \mod 5$, where $b^{-1}$ is the multiplicative inverse of $b$ modulo $5$.

Therefore, in either case, we are done.

Example

  • Let us continue from $125$. So we have to add $a \times 10^3 + 125$ for some $a$. Here, note that $1000$ leaves the remainder $3 \times 125$ when divided by $5^4 = 625$ so $b = 3$ and $L$ leaves the remainder $1 \times 125$ when divided by $625$, so $c = 1$. So $b^{-1} = 2$(since $2 \times 3 = 1 \mod 5$) and $b^{-1} \times -c = -2 = 3 \mod 5$. Check that $3125$ is a four digit multiple of $625$.

  • Next, we want a five digit multiple of $5^5 = 3125$. Here, we have $c = 0$ because $L = 3125$ is a multiple (in fact equal) to $3125$, so we have $a = 5$. Check that $53125$ is a multiple of $3125$.

  • Next, we want a six digit multiple of $5^6 = 15625$. Here, check that $L =53125$ , $c = 2$ and $ b= 2$ as well, so $b^{-1} = 3$ and $3 \times -2 = -6 \equiv 4$ so $453125$ is a multiple of $15625$.

Conclusion

Hence, for all $n$, there exists a multiple of $5^n$ which has exactly $n$ digits, and furthermore consists only of the digits $1,2,3,4,5$ by construction.

Addendum

Maybe the approach might seem a little arbitrary. I actually got the idea from another question I had solved about eight and a half years back (and wrote down the first $21$ terms on the school board!) : Show that there is a multiple of $2^n$ that consists only of the digits $6$ and $7$.

The style of proof there was exactly the same : take such a multiple of $2^n$ and adjoin either a $6$ or $7$ on the left so that things work out for the next power.

Last but not the least, note that the post attached in the comments to the question addresses this question but does not give a proof. Rather, it uses this fact to prove that every number not ending with zero has a multiple with no zero in its representation. In fact, as pointed out, such a number can also be made to consist solely of the digits $1,2,3,4,5,6,7$.

$\endgroup$

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.