Existance of multiple of $n$ with only 0 and 1 as it's digits

Question

Possible Duplicate:
Proof that a natural number multiplied by some integer results in a number with only one and zero as digits

I read this somewhere recently:

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?

Answer 1

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.

Answer 2

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)

In general if n is indivisible by 2 and 5, there exists a multiple of n that is written as repeated sequences of digits. For example n has a multiple that is in the form 249249249...249 The proof is very similar to the previous argument