1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ The number of primes $2,3,\cdots, 97$ is $25$, not $26$. $\endgroup$ – mathlove Aug 28 '14 at 14:47
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.