Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

marked as duplicate by rschwieb, Sasha, no identity, Hagen von Eitzen, EuYu Nov 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 2

up vote 12 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.