Take the 2-minute tour ×

I recently solved a problem, which says that,

a positive integer can be multiplied with another integer resulting in a positive integer that is composed only of one and zero as digits.

How can I prove that this is true(currently I assume that it is). Also, is it possible to establish an upper bound on the length(number of digits) of the number generated?

Thanks !

share|improve this question
add comment

2 Answers

up vote 33 down vote accepted

Not only is it possible to find a multiple of $n$ whose decimal expansion consists solely of $0$s and $1$s, it is possible to arrange for all the $1$s to come before all the $0$s.

Suppose first that $n$ is coprime to $10$. Then by Fermat–Euler, $10^{\varphi (9n)} \equiv 1 \pmod{9n}$. Thus $(10^{\varphi (9n)} -1)/9 \equiv 0 \pmod{n}$, and so there is a multiple of $n$ which consists solely of $1$s, namely $(10^{\varphi (9n)} -1)/9$.

Now consider the opposite case that $n=2^a 5^b$ for some natural $a, b$. Then some multiple of $n$ is a power of $10$: either $2^{b-a}n$ or $5^{a-b}n$, depending on whether $a$ or $b$ is greater.

Thus for general $n$, we can express $n$ as $2^a 5^b m$, where $m$ is coprime to $10$. Then we can find a multiple of $m$ which is a string of $1$s and a multiple of $2^a 5^b$ which is a power of $10$, and hence a multiple of $n$ which is a string of $1$s followed by a string of $0$s. Specifically, there are $\varphi (9m)$ $1$s and $\max(a,b)$ $0$s, so $\varphi (9m)+\max(a,b)$ gives an upper bound on the number of digits needed.

share|improve this answer
Awesome! Thank you for explaining in such detail :). –  Priyank Bhatnagar Nov 20 '11 at 13:53
add comment

Here is an alternate solution, which is based on the Pigeon principle:

List all the numbers 1, 11, 111, ... , 111...1 where the last one contains $n+1$ ones.

Look now at their remainders when divided by $n$. By the pigeon principle, two of them have the same remainder. But then their difference is of the form $1111..100000..0$ and is divisible by $n$..

share|improve this answer
This solution is a lot simpler. It needs more votes :) –  wircho Nov 20 '11 at 16:50
True, but there is always a price to pay for simplicity...The other solution yields extra information: you can actually find how many 1's and 0's you need ;) –  N. S. Nov 20 '11 at 17:03
Very intuitive! :) Thanks for sharing this :) –  Priyank Bhatnagar Nov 20 '11 at 18:05
+1 though that'd be the Pigeon hole principle. –  Mark Hurd Nov 21 '11 at 6:08
add comment

Your Answer


