# 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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 2 Answers

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.

Thinking in terms of prime numbers is not the way to attack this question. Instead:

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