# Show that there exists $i$ and $j$ with $1 \leq i<j \leq 51$ satisfying $a_i$ divides $a_j$. [duplicate]

Let $$a_1 be the given distinct natural numbers such that $$1 \leq a_i \leq 100$$ for all $$i=1,2,....,51$$. Then show that there exists $$i$$ and $$j$$ with $$1 \leq i satisfying $$a_i$$ divides $$a_j$$.

There are $$25$$ primes less than $$100$$. So we must take the set $$\{a_1,...,a_{51}\}$$ such that the set does not contain all $$25$$ primes. Because if the set contains all $$25$$ primes then any number other than these prime would divisible by one of the prime. But from here I can not proceed further. Please help me to solve this.

## marked as duplicate by darij grinberg, Gerry Myerson elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 31 at 9:25

We can divide the numbers $$1$$ to $$100$$ into $$50$$ different sets. First, put each odd number into a different set. Then, for some set with an odd number $$n$$, also place all numbers of the form $$2^k n$$ in the set, where $$2^k n$$ is between $$1$$ and $$100$$. Note that for any pair of numbers in the same set, one divides the other (as one of them will be $$2^a$$ times the other for some $$a$$).
Now by the pigeonhole principle, some set must contain $$2$$ numbers from $$a_i$$ since there are 50 sets. But then one of these divides the other, finishing the problem.
Hint: Partition $$\{1,2,\dots,100\}$$ into sets of the form $$\{m,2m,4m,8m,\dots\}$$ where $$m$$ is odd. There are 50 odd numbers between 1 and 100 inclusive, so ...