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?


1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .