Every positive integer divide some number whose representation (base 10) contains only zeroes and ones.
One can prove that:
Consider the numbers 1, 11, 111, 1111, etc. up to 111… 1, where the
last number has n+1 digits. Call these numbers m1, m2, … , mn+1. Each has a
remainder when divided by n, and two of these remainders must be the same.
Because there are n+1 of them but only n values a remainder can take.
This is an application of the famous and useful “pigeonhole principle”;
Suppose the two numbers with the same remainder are mi and mj
, with i < j. Now subtract the smaller from the larger. The resulting number, mi−mj, consisting of j – i ones followed by i zeroes, must be a multiple of n.
But how to find the smallest answer? and effciently?