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

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?

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 2 Answers

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)

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

• Thanks for your quick reply, specially for the point you mentioned in the second paragraph! It was very interesting. – Mahdi Ghiasi Nov 9 '12 at 19:11