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?

Solutions Collecting From Web of "A natural number multiplied by some integer results in a number with only ones and zeros"

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.

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