Problem 8.3. (15 points) In one move, you can choose a natural number $x$ and cross out all natural numbers $y$ such that $|x-y|$ is a natural composite number. At the same time, $x$ can be chosen from already crossed out numbers.

What is the minimum number of moves needed to cross out all numbers from the natural number sequence?
Answer: 2.

Solution. First, note that one move is not enough, because if we choose some natural number $x$, then the number $y=x$ will remain unchecked. Let's prove that two moves are enough.

We will look for two suitable numbers $x_{1}$ and $x_{2}$ of different parity. Then one of the differences $\left|y-x_{1}\right|$ or $\left|y-x_{2}\right|$ will be even. This means it will be composite - except for the cases when it equals 2 or 0. These cases need to be considered separately. For $y=x_{1}-2, y=x_{1}$, and $y=x_{1}+2$, the difference $\left|y-x_{2}\right|$ must be a composite number; and for $y=x_{2}-2, y=x_{2}$, and $y=x_{2}+2$, the difference $\left|y-x_{1}\right|$ must be a composite number.

In any case, it is sufficient for the differences $\left|x_{1}-x_{2}-2\right|, \left|x_{1}-x_{2}\right|$, and $\left|x_{1}-x_{2}+2\right|$ to be odd composite numbers. Since the expressions under the modulus cannot have different signs (otherwise one of them would be equal to 1), they must be three consecutive odd composite numbers.

Now it is enough to find three consecutive odd composite numbers $a-2, a, a+2$ (or even just prove that such numbers exist). Then we can choose, for example, $x_{1}=a+1$ and $x_{2}=1$ and get the required result.

There are different ways to prove that three consecutive odd composite numbers exist. Here are some of them.

Method 1. Consider the consecutive odd numbers $7!+3, 7!+5$, and $7!+7$. They are divisible by the prime numbers 3, 5, and 7, respectively, but are not equal to them, so they are composite.

Method 2. If we assume that $a-2$ is divisible by 3, $a$ is divisible by 5, and $a+2$ is divisible by 7, then the number $a$ must give remainders 2, 0, and 5 when divided by 3, 5, and 7, respectively, and a remainder of 1 when divided by 2. By the Chinese Remainder Theorem, there are infinitely many such $a$, and they form an arithmetic progression with a common difference of $2 \cdot 3 \cdot 5 \cdot 7 = 210$. The first such number is obviously $a=5$, but it does not work; the next one is $a=215$, which gives the triplet of composites $213, 215, 217$.

Method 3. We can also try odd numbers and find a suitable triplet. The smallest such triplet is $91, 93, 95$, which corresponds to $x_{1}=1$ and $x_{2}=94$.

## Criteria

The highest applicable criterion is used:

15 p. Any complete solution to the problem.

0 p. Proved that one move is not enough.

0 p. Only the answer is provided.