Show that for every integer $n$ there is a multiple of $n$ that has only $0s$ and $1s$ in its decimal expansion.

Question

Can anyone please explain this example as I tried a lot to understand it but I can't!

The problem:

Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion.

The Solution of the book:

Let $n$ be a positive integer. Consider the $n + 1$ integers $1, 11,$ $111, ..., 1111, ...$ (where the last integer in this list is the integer with $n + 1$ $\ 1s$ in its decimal expansion). Note that there are $n$ possible remainders when an integer is divided by $n$. Because there are $n + 1$ integers in this list, by the pigeonhole principle there must be two with the same remainder when divided by $n$. The larger of these integers less the smaller one is a multiple of $n$, which has a decimal expansion consisting entirely of $0s$ and $1s$.

This problem from Discrete Mathematics and its application's for Rosen

Answer 1

Suppose, say, that $n=3$. Consider the four numbers $1$, $11$, $111$, and $1\,111$. What are the remainders of the division of these numbers by $3$? They are $1$, $2$, $0$, and $1$ respectively. The remainder $1$ appears twice (corresponding to the numbers $1$ and $1\,111$). So, $1\,111-1(=1\,110)$ is a multiple of $3$.

The same idea works with every $n$.

Answer 2

I'll go through the books solution for $n=12$. This should convince you in general.

Consider the $13$ numbers $1; 11;111;1111;11111;111111;1111111;11111111;111111111;1111111111;11111111111;111111111111;1111111111111;$

There are thirteeen numbers. They each have a remainder when divided by $12$. There are only twelve such remainders so at least two of them must be the same.

The remainders are:

$1;11;3; 7;11;3;7;11;3;7;11;3;7$.

Many of them are the same. For example $1111$ has remainder $7$. So $1111 = 12k + 7$ for some $k$ (as it turns out $1111= 12*92+7$) and $1111111$ also has remainder $7$. So $1111111 = 12j + 7$ for some $j$ (as it turns out $1111111 = 12*92592 + 7$).

So that means $1110000=11111111 -1111 = (12*j + 7)-(12k +7) = 12j -12k = 12(j-k)$ and is a multiple of $12$.

In this case $1110000 =1111111-1111 = (12*92592 + 7)-(12*92 + 7) = 12(92592-92) = 12(92500)$

Actually we could have done this at the very first repeated remainder.

$11$ and $11111$ both have remainder $11$. $11= 0*12 + 11$ and $11111 = 12*925 + 11$. so $11111-11 = 11100 = (12*925+11) -(0*12+11) = 12(925-0) = 12*925$.

Ans so we can keep adding $0$s and multiply be $10$....

More complicated would be $111111111111$ and $111111111$ both have $7$ as remainders and $111111$ and $111$ have $3$ as remainders. So $111111111111= 12*j+7$ and $111111111=12*k + 7$ and $111111=12*m+3$ and $111=12*n+3$ so

$111111111111-111111111+111111-111 = 111000111000 = (12j+7)-(12k+7)+ (12m+3)-(12n+3) = 12(j-k+m-n)$ and indeed. $\frac {111000111000}{12} = 9250009250$

Answer 3

Here's a way I used to explain this to myself - Let n be a positive integer. Let's consider n+1 numbers of form 1, 11, 111, 1111, 1111 .... where last integer in this list is an integer with n+1 1s.

By the pigeonhole principle, there must be at least 2 numbers in this list of n+1 numbers that have the same remainder when divided by n.

Let these numbers be a & b.

a = 1...1 = Q.n + r, where Q is some integer and r is some integer < n

b = 1.....1 - Q'.n + r, where Q' is some integer and r is some integer < n (r is common remainder)

b > a

b - a = 111...11...11 - 11..111 = 111...00..000 = n(Q' - Q) + r - r = n.(Q' - Q)

=> b - a is a multiple of n that has only 0s and 1s in it's decimal.