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 1


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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .