Теория чисел на ЮМШ

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

2. Выпишем остатки от деления на 9 и на 27: легко убедиться, что это 2-периодические последовательности и соответственно.
Поэтому число не делится на 3 при нечетных , делится на 3, но не на 9 при и делится на 9, но не на 27 при четных .
То есть если — степень вхождения 3 в число , то , а дальше и .
Отсюда легко видеть, что наибольшее такое, что равно 2022, то есть — последняя среди разностей вида не кратная .

3. Пусть , тогда - нечетное число.
Заметим, что ,значит, достаточно показать, что существует число, проделывая операцию из условия над которым мы не получим 2.
Рассмотрим числа вида , где НОД

Нетрудно заметить, что
То есть числа вида , где НОД переходят в себя, но число 2 не имеет такого вида, поэтому полином нестабилен по модулю , если является квадратом нечётного числа.

4. Индукцией по докажем, что для многочлен стабилен.
Обозначим через , то что
База

Таким образом, имеем цикл длины 3 везде одинаковый.
Переход
Пусть по модулю многочлен стабилизируется так, что всегда встретится
Тогда по модулю остаток будет
, что не зависит от , при
, что бывает по базе индукции, поэтому многочлен стабилизируется и по модулю .