Теория чисел на СПБГУ: десятичная запись, оценка+пример, разные системы счисления

Сделаем два замечания.

1) нечетно. Действительно, пусть четно. Среди семи чисел всегда есть три числа одной четности, и по условию они должны быть попарно соединены. Но на картинке нет циклов длины 3.

2) Если — простой делитель то среди четырех последовательно соединенных чисел существует пара соседних, сумма которых не кратна Возьмем цепочку последовательно соединенных чисел. По условию

Тогда числа и тоже соединены, то есть на картинке получился цикл длины 4, которого там нет.

Из 1) и 2) вытекает, что число имеет по крайней мере два различных нечетных простых делителя. Пусть их ровно два (скажем, и Покажем, что они отличны от 3. Допустим, например, что Не более двух чисел делятся на 3 (если их три, то они образуют цикл). Остальные числа разобьем на две группы, дающие при делении на 3 остатки 1 и 2. Одна из этих групп пуста, иначе любое число из меньшей группы будет соединено по крайней мере с тремя числами из другой группы, что невозможно. Сумма чисел из одной группы на 3 не делится. Поэтому существует трехзвенная цепочка, в которой сумма любой пары соединенных чисел не кратна 3 и, значит, делится на Но это противоречит 2).

Таким образом, если имеет ровно два различных нечетных простых делителя, то Если же таких делителей больше двух, то . Расстановка для приведена на рисунке.