Выбор модуля для доказательства делимости / простоты / степени

Обозначим число из условия через Предположим, что существуют такие натуральные числа что Тогда поскольку для любого разность делится на При всех числа и дают одинаковые остатки при делении на следовательно, при всех числа и дают одинаковые остатки при делении на Значит, при всех т.е. последовательность периодическая с периодом

Теперь предположим, что последовательность состоит из различных чисел. Так как то т.е. Далее, при получаем, что не кратно следовательно, не кратно В частности, при Пусть — это все решения уравнения Так как то Значит, все числа в последовательности дают одинаковый остаток при делении на а значит, и при делении на Следовательно, То есть и для любого

Предположим, что для некоторого Так как все дают одинаковый остаток при делении на выполняется равенство где Но тогда то есть Но противоречие. Значит, при всех Тогда или — это арифметическая последовательность с разностью или найдётся такое что Во втором случае мы уже доказали в начале решения, что последовательность получится периодическая. Что и требовалось доказать.