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$
 A: 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$.
A: Hint $\rm\ \ x\overset{f}\mapsto 10\, x + 3\pmod{ 1001}\ $ has orbit $\rm\ 0\overset{f}\mapsto3\overset{f}\mapsto33\overset{f}\mapsto 333\,\ldots\,$ which must cycle back to $\:0\:$ because $\,f\,$ is invertible - with inverse $\rm\:x\mapsto (x-3)/10\equiv 100\ (3-x)\:;\: $ i.e. being an invertible map on a finite set, $\,f\,$ 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,\,(0,\ 3,\ 33,\ 333,\ 330,\ 300),\,$ so 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. See here for a less trivial example, and see this list for further examples.
