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?


2 Answers 2


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

  • 4
    $\begingroup$ This solution is a lot simpler. It needs more votes :) $\endgroup$
    – wircho
    Nov 20, 2011 at 16:50
  • 8
    $\begingroup$ 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 ;) $\endgroup$
    – N. S.
    Nov 20, 2011 at 17:03
  • 1
    $\begingroup$ Very intuitive! :) Thanks for sharing this :) $\endgroup$ Nov 20, 2011 at 18:05
  • 22
    $\begingroup$ +1 though that'd be the Pigeon hole principle. $\endgroup$
    – Mark Hurd
    Nov 21, 2011 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.

  • $\begingroup$ Awesome! Thank you for explaining in such detail :). $\endgroup$ Nov 20, 2011 at 13:53

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.