Least positive integer $n$ such that any set of $n$ pairwise relatively prime $>$ $1$ and $<$ $2005$ contains at least one prime number.

Find the least positive integer $$n$$ such that any set of $$n$$ pairwise relatively prime integers greater than $$1$$ and less than $$2005$$ contains at least one prime number.

The given solution of the above problem opens with the following line:

The example $$2^2, 3^2, 5^2,\dots, 43^2$$ where we considered the squares of the first $$14$$ prime numbers, shows that $$n\geq 15$$.

How does this happen? Why are we considering squares of primes?

The condition is: If we pick any arbitrary set of $n$ numbers so that all numbers in set are pairwise relatively prime then there exists a prime number in that set.

So, if $n \le 14$, then when we pick the set $\{ 2^2,3^2, \ldots , 43^2 \}$ (which has $14$ numbers in set) where there is no prime in this set, which contradicts to our condition. Thus, $n \ge 15$.

They choose squares of primes to guarantee that

• All numbers are pairwise relatively prime.
• The set doesn't contain any prime number.

If we can find set $A$ that guarantee this, then $n \ge |A|+1$ (the proof using contradiction is similar to when $|A|=14$). Thus, it suffices to find set $A$ with maximal number of elements.

Note that we can choose differently $$B= \{ 2 \cdot 997, 3 \cdot 661, 5 \cdot 397, 7 \cdot 269, 11 \cdot 173, 13 \cdot 151, 17 \cdot 113, 19 \cdot 103, 23 \cdot 83, 29 \cdot 67, 31 \cdot 61, 37 \cdot 53, 41 \cdot 47, 43^2 \}.$$ This also shows that $n \ge |B|+1=15$. It seems that $n=15$ is the smallest possible.

The randomly chosen set $A$ is to show that $n \ge 15$. But that's not all the problem required, we also need prove that $n=15$ is the smallest possible.