1. In the picture, several circles are drawn, connected by segments. Kostya chooses a natural number \( n \) and places different natural numbers in the circles so that for all these numbers the following property holds:

if numbers \( a \) and \( b \) are not connected by a segment, then the sum \( a + b \) must be coprime with \( n \), and if they are connected, then the numbers \( a + b \) and \( n \) must have a common natural divisor greater than 1. For what smallest \( n \) does such an arrangement exist?

![](https://cdn.mathpix.com/cropped/2024_05_06_6bce8335c6b594326f89g-21.jpg?height=220&width=217&top_left_y=604&top_left_x=931)
Answer: $n=15$.

Solution. We will make two observations.

1) $n$ is odd. Indeed, suppose $n$ is even. Among any five numbers, there are always three numbers of the same parity, and by the condition, they must be pairwise connected. But there are no cycles of length 3 in the picture.
2) $n$ has at least two distinct prime divisors. Suppose $n$ is a power of a prime number $p$. Take a chain $(a, b, c, d)$ of sequentially connected numbers. By the condition,

$$
a+d=(a+b)-(b+c)+(c+d) \vdots p
$$

Then the numbers $a$ and $d$ are also connected, which means there is a cycle of length 4 in the picture, which is not there.

Thus, the number $n$ has at least two distinct odd prime divisors, hence $n \geqslant 15$. The arrangement for $n=15$ is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_6bce8335c6b594326f89g-21.jpg?height=337&width=351&top_left_y=1373&top_left_x=864)