combinatorics - Prove that for any given positive integer $n$,there exists a number having digits $0,1$ which is divisible by $n$.

Prove that for any given positive integer $n$,there exists a number having digits $0,1$ which is divisible by $n$.

Let that number be of the general form: $x=\overline {b_kb_{k-1}...b_1b_0}$ where $b_i\in \{0,1\}$.How can we construct $x$ to be divisible by the given $n$?

Answer

Let

$$a_k = \underbrace{111...11}_{k} = {10^k-1\over 9}$$

So, among $a_1,a_2,...a_{n+1}$ two must have the same remainder modulo $n$, say $a_i$ and $a_j$ and $i>j$. Thus

$$n\mid a_i-a_j ={10^i-10^j\over 9} =10^j{10^{i-j}-1\over 9}= \underbrace{111...11}_{i-j}\underbrace{000...00}_{j}$$