1. In the picture, several circles are drawn, connected by segments. Nastl 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 difference \( 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_0b0e793e58d3be992fedg-18.jpg?height=140&width=251&top_left_y=598&top_left_x=914)
Answer: $n=3 \cdot 5 \cdot 7=105$.

Solution. We will make two observations.

1) $n$ is odd. Indeed, suppose $n$ is even. Among the six 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 diagram.
2) If $p$ is a prime divisor of $n$, then among three consecutively connected numbers, there exists a pair of adjacent numbers whose difference is not divisible by $p$. Suppose $(a, b, c)$ is a chain of consecutively connected numbers where $a-b$ and $b-c$ are divisible by $p$. Then $a-c=(a-b)+(b-c) \vdots p$. Therefore, $(a, b, c)$ forms a three-link cycle, which is impossible.

We will show that the number $n$ has at least three distinct prime divisors. Let $p$ be a prime divisor of $n$. There are no more than three distinct pairs $(a, b)$ for which $a-b \vdots p$. If there were 4 such pairs, then some two of them would intersect, which contradicts 2). But in total, 7 pairs of numbers are connected by segments, so $n$ has at least three distinct prime divisors. By 1), the smallest possible values for them are $3, 5, 7$, that is, $n \geqslant 3 \cdot 5 \cdot 7=105$. The arrangement for $n=105$ is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_0b0e793e58d3be992fedg-18.jpg?height=197&width=311&top_left_y=1398&top_left_x=884)