Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
2  
Which part of the solution don't you understand? –  Robert Israel Sep 21 '11 at 0:25
3  
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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