Pairwise coprime

Intuitively, pay attention that there are $14$ primes less than $\sqrt{2018} \approx 45$ . If we try to choose numbers, in the range $1$ to $2018$ , wisely, such that we neither take a prime nor a number that is made of more than a single prime, we see that $15$ is the most we can achieve. The set is $A=\{1,2^2,3^2,5^2,7^2,11^2,13^2,17^2,19^2,23^2,29^2,31^2,37^2,41^2,43^2\}$ . Any number that is not in the set would be either a prime, in the range $1$ to $2018$ , or is relatively not prime with respect to at least one member of the set.

Pick any natural $m \geq 2$ . Let $\{a_{i}\}_{i=1}^{m}$ be an increasing sequence of distinct, not prime, pairwise coprime naturals. Let $\{p_{i}\}_{i=1}^{\infty}$ be the sequence of primes in increasing order. Let $b_{1} = 1$ , and for $2 \leq i \leq m$ let $b_{i}$ be the smallest prime dividing $a_{i}$ (the existence of $b_{i}$ follows from every natural greater than one having at least one prime divisor, together with the well-ordering principle). So, $b_{2},...,b_{m}$ is a sequence of $m - 1$ prime numbers. Suppose that for each $2 \leq i \leq m$ we have $b_{i} < p_{m - 1}$ . If $m = 2$ , this implies $b_{2}$ is a prime smaller than $2$ , a contradiction. If $m > 2$ , since there are only $m-2$ primes less than $p_{m-1}$ , the pigeonhole principle guarantees $2 \leq i,j\ \leq m$ such that $i \neq j$ but $b_{i} = b_{j}$ . But it follows then that $a_{i}$ and $a_{j}$ share a prime factor, contradicting that they are pairwise coprime. Therefore there must actually be $2 \leq k \leq m$ such that $b_{k} \geq p_{m-1}$ . Since $b_{k}$ divides $a_{k}$ we can write $a_{k}=nb_{k}$ for some natural $n$ . Since $a_{k}$ is not prime, it follows that $n > 1$ , so that we can pick a prime $p$ dividing $n$ (note that we hence have $p \leq n$ ). But it follows that $p$ also divides $a_{k}$ , and therefore $b_{k} \leq p \leq n$ (since $b_{k}$ was chosen to be the smallest prime dividing $a_{k}$ ). Therefore, $a_{k} = nb_{k} \geq b_{k}^{2} \geq p_{m-1}^{2}$ . Since $\{a_{i}\}_{i=1}^{m}$ is increasing, it follows that $a_{m} \geq a_{k} \geq p_{m-1}^{2}$ .

Fix any natural $n > 1$ . Suppose that $m \geq 2$ and $p_{m-1}^{2} \geq n$ . Then, if it were possible to choose $m$ distinct, not prime, and pairwise coprime naturals smaller than $n$ , it would follow from the above argument that the largest of these (say $k$ ) satisfies $n > k \geq p_{m-1}^{2}$ , contradicting that $p_{m-1}^{2} \geq n$ . Therefore, in fact, every choice of $m$ distinct and pairwise coprime naturals smaller than $n$ must include at least one prime.

Conversely, if every choice of $m$ distinct and pairwise coprime naturals smaller than $n$ must include at least one prime, then we must have $m > 1$ . Further, since $1,p_{1}^{2},...,p_{m-1}^{2}$ is asequence of $m$ distinct and pairwise coprime naturals with no primes, it must contain an element at least as large as n. Since $p_{m-1}^{2}$ is its largest element, it follows that $p_{m-1}^{2} \geq n$ .

So, finally, it follows that every choice of $m$ distinct and pairwise coprime naturals smaller than $n$ contains a prime if and only if $m > 1$ and $p_{m-1}^{2} \geq n$ . So, applying the result to this problem, we simply need to find the smallest $m > 1$ with $p_{m-1}^{2} \geq 2018$ , which is $m = 16$ .