1
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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