Question

Докажите, что для каждого натурального n существует множество S положительных целых чисел n, такое, что для любых двух различных a,b из S, a-b делит a и b, но не делит ни один из других элементов S

Answer 1

Идея состоит в том, чтобы найти последовательность $d_1, \dots, d_{n-1}$ "разностей", такую, что выполняются следующие два условия. Пусть $s_i = d_1 + \dots + d_{i-1}$, а $t_{i,j} = d_i + \dots + d_{j-1}$ для $i \le j$. Тогда мы хотим, чтобы

1. Никакие два из $t_{i,j}$ не делят друг друга

2. Существует целое число $a$, удовлетворяющее

$\[ a \equiv -s_i \pmod{t_{i,j}} \quad \forall i \le j \]$

Тогда последовательность $a+s_1, a+s_2, ..., a+s_n$ будет работать.

Например, при $n=3$ можно взять $(d_1,d_2)=(2,3)$, что дает

$10 \overbrace{\underbrace{\qquad}_2 12 \underbrace{\qquad}_3}^5 15$

потому что единственные условия, которым мы должны соответствовать, - это

$a \equiv 0 \bmod 2 , \ \ a \equiv 0 \bmod 5 , \ \ a \equiv -2 \bmod 3$

Мы можем индуктивно построить $d_i$. Чтобы перейти от $n$ к $n+1$, возьмем $d_1, \dots, d_{n-1}$, пусть $M$- кратное $\prod\limits_{i=1}^{n-1} d_i$ и пусть $p \nmid M$. Тогда мы утверждаем, что $d_1M, d_2M, \dots, d_{n-1}M, p$ - такая разностная последовательность. Например, предыдущий пример можно расширить следующим образом

$a \overbrace{\underbrace{\qquad}_{600} b \overbrace{\underbrace{\qquad}_{900} c \underbrace{\qquad}_{7}}^{907}}^{1507} d$

Новые числа $p$, $p+Md_{n-1}$, $p+Md_{n-2},\dots$ являются относительно простыми по отношению ко всем остальным. Следовательно, (1) остается в силе. Чтобы убедиться в справедливости (2), заметим, что мы по-прежнему можем получить семейство решений для первых $n$ членов, а затем последний $n+1$ член может быть найден с помощью Китайской теореме об остатке, поскольку все новые $p+Md_k$ являются простыми по отношению ко всем остальным