Prove that every subset A of the set {2, 3, ... 99, 100} with |A| > 26, has at least one pair of integers that is not relatively prime.
2, 3, 5 .. , there are 26 primes below 100. Can someone give me some hints for solving this please. I can see there are half odd/half even, non primes multiple of primes etc
Think about prime factorizations. Here's an analogy: Suppose you have a list of at least 27 English words (or strings of letters, really). There are only 26 letters in the English alphabet, so at least two words contain the same letter.
Alternate statement of the pigeonhole principle:
If $f:X\to Y$ is a function with $|X|>|Y|$, then for some $x_1,x_2\in X$, $x_1\neq x_2$ and $f(x_1)=f(x_2)$.
Let $S=\{2,3,\dots,100\}$. Let $P$ be the primes in $S$. Define $f:S\to P$ by taking $f(n)$ to be the smallest prime dividing $n$. Then $f_{\mid A}:A\to P$ and $|A|>26=|P|$, so for some $m\neq n, m,n\in A$ we have $f(n)=f(m)$. But that means $n,m$ have a common least prime divisor.
