We have n positive integers greater than 1 and less than 10000 such that neither of them is prime but any two of them are relative prime. Find the maximum value of n.
We claim the answer is 25.
To show that 25 is achievable, take the set S={p2:p prime, p<100}. There are 25 primes less than 100, so |S|=25, and it is clear that its elements are composite, in the desired range, and pairwise relatively prime.
To see that nothing greater works, observe that if n is composite and its smallest prime factor is p>100, then n≥p2>10000. Thus, if S is a set with the desired property, then the smallest prime factor of each element of S is less than 100. However, all elements of S must have distinct smallest prime factors, so S has at most 25 elements.