# Prove two numbers of a set will evenly divide the other

We have a set A of numbers 1, 2, 3... to 200

The question is asking me to prove that if I choose 101 numbers from the set, there will be two such that one evenly divides the other.

I know this could be the pigeonhole principle question. I could prove by contradiction that no two numbers will evenly divide each other. Assume I take 101 numbers, I can't take all the odd numbers because there is only 100 of them, so there will be an even number. I think this goes no where.

Using a direct proof if I choose 101 numbers, I will get either 100 even + 1 odd or 100 odd + 1 even. In order for two numbers to evenly divide each other I would choose the 100 even, and there is a big probability that two will be even, but if I have 100 odd + 1 even, there will be only 1 even... So I'm not sure how to solve this...

• Note: 'evenly divides' doesn't mean one of the numbers are even, it means that one divides another with 0 remainder. (I'm not sure if this is what you thought, but just in case). Pick 101 elements of $A$ (I'm assuming they're all distinct, otherwise the result is trivial). What can you say about the smallest number $x$ you've picked? It's at least ... Now can you apply the pigeonhole principle to remainders of the other 100 numbers modulo $x$? – ah11950 Apr 26 '14 at 7:10
• @ah11950 Right. Major misunderstanding there! – user3511965 Apr 26 '14 at 7:10
• No worries. 'Evenly divides' isn't ever a term I would use... Give the question another shot now! You at least have the right idea thinking you'll need to apply pigeonhole. – ah11950 Apr 26 '14 at 7:11
• @ah11950 Ok, but can I still do the worst case of 100 even + 1 odd and 100 odd + 1 even or does that not matter at all? – user3511965 Apr 26 '14 at 7:13
• Why 100 boxes? (This is pretty much correct, but needs a bit of justification - it's actually at most 100 boxes). If $S$ is your subset of 101 numbers in $A$, $x$ the minimal element of $S$, and $m, n \in S\setminus \{x\}$, what can you conclude if $m \equiv n\; (\text{mod}\; x)$? Indeed, does this necessarily occur? – ah11950 Apr 26 '14 at 7:18

Pick $$101$$ elements from $$A$$, label them $$a_1,\ldots, a_{101}$$. We can assume that $$a_1 < \ldots < a_{100} < a_{101}$$. Since we have $$101$$ distinct elements, $$a_1 \leq 99$$.

Consider the set of remainders upon division by $$a_1$$. Since $$a_1 \leq 99$$, there are at most $$98$$ such remainders. Let $$r_2$$ be the remainder upon dividing $$a_2$$ by $$a_1$$, $$r_3$$ the remainder upon dividing $$a_3$$ by $$a_1, \ldots, r_{101}$$ the remainder upon dividing $$a_{101}$$ by $$a_1$$.

We have $$101$$ remainders $$r_1,\ldots ,r_{101}$$ (pigeons), and at most $$98$$ possible remainders (pigeonholes) upon dividing by $$a_1$$. Thus, by the pigeonhole principle, $$r_i = r_j$$ for some $$1\leq i < j \leq 101$$. Now what can you say about the number $$a_j - a_i$$?

• but how to show that there will be two such that one evenly divides the other – user469065 Oct 1 '19 at 16:22

Hint: The boxes will have labels $1$, $3$, $5$, and so on up to $199$. Odd labels! Note that there are $100$ boxes.

Box 1: Contains $1,2,4,8,16, 32,\dots$

Box 3: Contains $3,6,12,24, 48, \dots$

Box 5: Contains $5,10,20, 40,\dots$.

And so on.

Box 99: Contains $99,198$

Boxes 101, 103, and so on are pretty boring. Box 101 only contains the number $101$, Box 103 only contains $103$, and so on.

• Hmmm... why no even boxes? – user3511965 Apr 26 '14 at 7:24
• These are just labels for the boxes. They happen to be convenient. Note that (for example) if $a$ and $b$ are in box 5, then $a$ divides $b$ or $b$ divides $a$. Same with the other boxes. – André Nicolas Apr 26 '14 at 7:27