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

Рассмотрим остатки при делении на . Заметим, что они сами должны давать одинаковый остаток при делении , поскольку

То есть числа дают тот же остаток при делении на , что и само число . Отсюда делаем вывод, что это обязательно числа и в каком-то порядке (все остальные остатки при делении на встречаются в единственном экземпляре). Теперь рассмотрим остаток при делении на . Заметим, что

из доказанного выше. В каждом из случаев первое слагаемое кратно , как и , то есть числа и (или, что то же самое, ) дают один и тот же остаток при делении на . Получили, что даёт остаток при делении на .

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

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