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, . . . , 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.


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.