Prove that if 51 positive integers between 1 and 100 are chosen, then one of them must divide another.

Question

Given $51$ integers $a_1, a_2, \ldots, a_{51}$ satisfying $1 \leq a_i \leq 100$. Prove that there exist $i$ and $j$ such that $a_i \mid a_j$.

I'm a little unsure how to approach this problem. Thanks for any help.

Answer 1

More explicit hint (than Andre's comment): each integer in $\{1,\ldots,100\}$ can be written as $2^mn$ where $$ n\in A=\{1,3,\ldots,99\}. $$ Note that $|A|=50$, exactly $1$ fewer than $51$. Can you see now how to apply the pigeonhole principle? In particular, if $x=2^{m_1}n$ and $y=2^{m_2}n$ where $n$ is the same for both $x$ and $y$, can you say something about the divisibility between $x$ and $y$?