# Prove at least two numbers $(a,b)$ exist such that $a|b$ or $b|a$.

We have this set : $$A=\{1,2,3, \dots , n\}$$

We choose $\left\lceil\frac{n}{2}\right\rceil+1$ numbers from $A$. Can we prove that at least two numbers exist that are divisible ? (In other words, either $a\mid b$ or $b\mid a$.)

Example : If $A = \{1,2,3,\dots ,20\}$ we must choose $11$ numbers to get at least two numbers divisible.

• It is obvious that $1|3$ – S.H.W Dec 26 '16 at 8:50
• My mean is GCD not HCF – S.H.W Dec 26 '16 at 8:51
• Greatest Common Divisor (GCD) = Highest Common Factor (HCF). Your last statement (in brackets) has slightly different from the rest of the question. – Swapnil Rustagi Dec 26 '16 at 8:54
• If $n$ is odd , for example $n=5$ we must choose $3$ numbers. – S.H.W Dec 26 '16 at 8:55
• Don't you mean $a\mid b$ or $b\mid a$? – Darth Geek Dec 26 '16 at 8:55

Yes it is true, but only if $n$ is even. There are a lot of counterexamples which are clearly mentioned in comments and other answers too that explains why $n$ can not be odd.

HINT: Try pigeonhole principle.

By factoring out as many $2's$ as possible, any number from the given set can be written as $2^k.a$ where $a$ is odd number and $k\ge0$.

For example $12=2^2\times 3$ and $3$ is odd. $28=2^2\times 7$ and $7$ is odd. $33=2^0\times 33$ and $33$ is odd etc.

Now $a$ can be any odd i.e. $1,3,5......$ From the given set and there will be $\frac{n}{2}$ of such numbers ($a$). So whenever you select $\frac{n}{2} + 1$th number there must be two numbers having the same value of $a$. For example $l=2^p\times a$ and $m=2^q\times a$.

When $p>q$ then $m|l$ and when $q>p$ then $l|m$.

• Can you explain "By factoring out as many 2's as possible, any number from the given set can be written as $2^k$" ? – S.H.W Dec 26 '16 at 9:42
• Can you determine $a$ and $k$ in your answer ? – S.H.W Dec 26 '16 at 9:47
• I'm sorry but I'm still unable to understand your solution . – S.H.W Dec 26 '16 at 9:49
• Okay , Thank you a lot. – S.H.W Dec 26 '16 at 9:59
• @S.H.W, now see the answer – I am Back Dec 26 '16 at 10:05

No, let $n=3$ such that $A = \{1,2,3\}$. Now we pick $\lfloor \frac{3}{2} \rfloor + 1 = 2$ numbers from $A$, being $2$ and $3$. These are relatively prime hence not divisible.

• Please check it again . – S.H.W Dec 26 '16 at 9:09
• @S.H.W are you also including pair of (3,1)? – Kanwaljit Singh Dec 26 '16 at 9:16
• Yes , (1,3) is valid – S.H.W Dec 26 '16 at 9:17
• And you are only assuming continues numbers starting from 1? – Kanwaljit Singh Dec 26 '16 at 9:18
• Your mean is natural numbers ? – S.H.W Dec 26 '16 at 9:18

For $n=2m+1>1$ choose $x$ for $m+1\leq x\leq 2m-1$ and choose $m$ and choose $2m+1.$ This gives $m+2$ numbers, no two of which are divisors of each other. For even $n,$ I dk.