# Looking for an explanation: Pigeonhole Principle-Among a sequence prove there is a number divisible by another number

Could someone provide an explanation for this problem? I have the answer, but I don't understand the reasoning behind it.

Q: Among the sequence $3, 33, 333, 3333,\dots$ prove that there is one number divisible by $1001$ (use the Pigeonhole Principle).

A:

Division by $1001 \Rightarrow$ (Use PP), there exist $2$ numbers in the sequence, say $a_i$ and $a_j$ ($1 \le i < j$) with same remainder

$a_{j-i}-10^i$

$a_j - a_i = a_{j-i}10^i$ is divisible by $1001$

$(1001, 10) = 1$, relatively prime

$\Rightarrow a_{j-i}$ is divisible by $1001$

-
Which part of the solution don't you understand? – Robert Israel Sep 21 '11 at 0:25
If it were some other divisor than $1001$, this would be a nice problem, but you don't need the pigeonhole principle to see that obviously $333333 = 333 \times 1001$ is divisible by $1001$... – Rahul Sep 21 '11 at 0:45

If you let $r_i$ be the remainder when $a_i$ is divided by $1001$, you get an infinite sequence of remainders, $\langle r_1,r_2,r_3\dots\rangle$. Consider the first $1002$ of these remainders: each one of them has to be one of the integers $0,1,2,\dots,1000$, and there are only $1001$ of these possible values. Thus, some two of the first $1002$ remainders must be equal. Let’s call them $r_i$ and $r_j$, where $1 \le i < j \le 1002$.

Let $q_i$ be the quotient when $a_i$ is divided by $1001$; then $a_i = 1001q_i + r_i$. Similarly, if $q_j$ is the quotient when $a_j$ is divided by $1001$, then $a_j = 1001q_j + r_j$. It follows that \begin{align*} a_j - a_i &= (1001q_j+r_j) - (1001q_i+r_i)\\ &= 1001(q_j-q_i)+(r_j-r_i)\\ &= 1001(q_j-q_i), \end{align*}

where the last step is justified because $r_j=r_i$. This shows that $a_j-a_i$ is a multiple of $1001$.

Now $a_j$ is a string of $j$ $3$’s, and $a_i$ is a string of $i$ $3$’s, so $a_j-a_i$ is a string of $j-i$ $3$’s followed by $i$ $0$’s. (If you’re not sure about this, look at some examples!) And $a_{j-i}$ is a string of $j-i$ $3$’s, so $a_j-a_i$ is $a_{j-i}$ followed by $i$ $0$’s. Each of those $i$ $0$’s represents one multiplication by $10$, so $a_j-a_i = a_{j-i}10^i$. Thus, $a_{j-i}10^i$ is a multiple of $1001$, or, more concisely, $1001\mid a_{j-i}10^i$.

Finally, you have a theorem that says that if $a\mid bc$, and $a$ and $b$ are relatively prime, then $a\mid c$. $1001$ and $10^i$ are relatively prime, so that theorem tells us that $1001 \mid a_{j-i}$, i.e., that $a_{j-i}$ is a multiple of $1001$.

-

Hint $\rm\ \ x\mapsto 10\ x + 3\pmod{ 1001}\$ has orbit $\rm\equiv\: 0,\ 3,\ 33,\ 333,\:\ldots$ which must cycle back to $\:0\:$ because the map is invertible - with inverse $\rm\:x\mapsto (x-3)/10\:\equiv\: 100\ (3-x)\:;\:$ i.e. being an invertible map on a finite set it is a permutation, whose orbits are cycles. Each time the sequence cycles back to zero we obtain an element of the sequence $\equiv 0\:,\:$ i.e. divisible by $1001.\,$ So there are infinitely many such elements. Though it is not needed, notice that the orbit of $\:0\:$ is a cycle of length $6,\,$ namely $\,(0,\ 3,\ 33,\ 333,\ 330,\ 300).\,$ So, in fact, every $6$'th element is divisible by $1001$.

Remark $\$ This cyclical structure of permutation orbits is a fundamental fact with widespread applications. Frequently this simple structure is overlooked, resulting in obfuscated arguments that amount to essentially reinventing the wheel / cycle.

-