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

Question

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 1

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

Answer 2

Note that $10^{k \, \varphi(n)} \equiv 1,$ where $\varphi$ is the Euler phi function and $k\in \mathbb{N}$, and then see that $$ \sum_{k=1}^n 10^{k \, \varphi(n)} \equiv 0 \pmod n $$ Thus the integer whose decimal expansion has a 1 at positions $k \, \varphi(n)$ for $k=1,\dots,n$ and zeros everywhere else is divisible by $n.$

Alas, this only works if $n$ is relative prime to 10, and needs to be modified otherwise.