# A natural number multiplied by some integer results in a number with only ones and zeros

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?

Here is an alternate solution, which is based on the pigeonhole 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 pigeonhole principle, two of them have the same remainder. But then their difference is of the form $1111..100000..0$ and is divisible by $n$..

• This solution is a lot simpler. It needs more votes :) 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 ;) Nov 20 '11 at 17:03
• Very intuitive! :) Thanks for sharing this :) Nov 20 '11 at 18:05
• +1 though that'd be the Pigeon hole principle. Nov 21 '11 at 6:08

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.

• Awesome! Thank you for explaining in such detail :). Nov 20 '11 at 13:53