# Existance of multiple of $n$ with only 0 and 1 as it's digits [duplicate]

For any natural number $n$, there exists a multiple of $n$, such that the multiple has only 0 and 1 as its digits.

$2 \to 10$

$3 \to 111$

$4 \to 100$

$5 \to 10$

$6 \to 1110$

$7 \to 1001$

Any ideas how to go about proving this?

## marked as duplicate by rschwieb, Sasha, Norbert, Hagen von Eitzen, EuYuNov 9 '12 at 21:15

Consider the numbers $a_1=1$, $a_2=11$, $a_3=111$, and so on. Let $r_1, r_2,r_3,$ and so on be the remainders when the $a_i$ are divided by $n$.
There are at most $n$ conceivable such remainders. So there must be two numbers $a_i$, $a_j$ such that $i\lt j$ and $r_i=r_j$. Their difference $a_j-a_i$ is divisible by $n$, and has only $0$'s and/or $1$'s. Moreover, all the $1$'s precede all the $0$'s.
Consider the numbers 1,11,111,...,111...11 (1 is repeated n+1 times). Since these are n+1 numbers we can use the pegionhole principle to deduce that 2 of them are congruent $modulo$ $n$. Find the absolute value of the difference between the 2 numbers that are congruent modulo n. The difference is made up of 1(s) and zeros. This number is also divisible by n. (done)