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 \); if 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-25.jpg?height=226&width=254&top_left_y=601&top_left_x=912)
Answer: $n=15$.

Solution. We will make two observations.

1) $n$ is odd. Indeed, suppose $n$ is even. If there are three even and three odd numbers, then each of these triples forms a cycle. Suppose there are four numbers $a, b, c, d$ of the same parity. Then all of them are pairwise connected, and we again get two three-link cycles - for example, $(a, b, c)$ and $(a, d, c)$. But there is only one such cycle in the picture.
2) $n$ has at least two distinct prime divisors. Suppose $n$ is a power of a prime number $p$. Consider 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 that 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-25.jpg?height=288&width=311&top_left_y=1438&top_left_x=881)