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?

Answer

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

Attribution
Source : Link , Question Author : Priyank Bhatnagar , Answer Author : Jyrki Lahtonen

Leave a Comment