3. Find the smallest natural number $k$ such that every $k$-element set of pairwise coprime three-digit numbers contains at least one prime number.
SOLUTION. For constructing a set of two-by-two coprime three-digit composite numbers with a large number of elements, we can use the fact that powers of two different prime numbers are coprime. The set

$$
\left\{2^{7}, 3^{5}, 5^{3}, 7^{3}, 11^{2}, 13^{2}, 17^{2}, 19^{2}, 23^{2}, 29^{2}, 31^{2}\right\}
$$

contains 11 two-by-two coprime three-digit numbers, and there is no prime number in it. For the next prime number 37, it holds that $37^{2}>1000$, so every composite three-digit number is divisible by at least one prime number less than 37.

We will prove that every set of at least twelve two-by-two coprime three-digit numbers already contains a prime number. The set of all composite three-digit numbers can be divided into 11 subsets $A_{2}, A_{3}, A_{5}, A_{7}, A_{11}, A_{13}, A_{17}, A_{19}, A_{23}, A_{29}, A_{31}$, where $A_{i}$ contains the numbers whose smallest prime factor is the number $i$. Any two different numbers from the same set $A_{i}$ are coprime. Let the set $B$ of three-digit two-by-two coprime numbers have at least 12 elements. If $B$ contained only composite numbers, by the Dirichlet principle, $B$ would contain two numbers from the same set $A_{i}$; these numbers would, however, be coprime. Therefore, the set $B$ must contain at least one prime number.

The sought smallest number $k$ is thus 12. 

## GUIDING AND SUPPLEMENTARY PROBLEMS: