# using the pigeon hole principle to prove that some integer with a sequence of ones and zeros is divisible by some d

Let $d$ be any fixed natural number. Show that there must exist an integer of the form $11\ldots1100\ldots 00$ (that is a integer whose digits consist of a sequence of $1$'s followed by $0$'s) which is divisible by $d$.

So If $x$ is the sequence integer the I know I want to show that:

$$x \equiv 0 \mod d$$

I know that the remainder are the boxes in the pigeon hole principles. But here I am stuck on how to proceed. any help?

## 1 Answer

Consider the first $d+1$ terms of this sequence

$$1, 11, 111, ...$$ and their remainders mod $d$. By the pigeonhole principle, we know that two of these must have the same remainder modulo $d$. Call them $a_i$ and $a_j$ where

$$a_i = \underbrace{1111...1}_\textrm{i ones}$$ $$a_j = \underbrace{1111...1}_\textrm{j ones}$$

and $i < j$. But then,

$$a_j - a_i = \underbrace{1111...1}_\textrm{j-i ones}\underbrace{0000...0}_\textrm{i zeroes}$$

and is divisible by $d$.