Базовый аппарат сравнений по модулю

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

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

Теперь докажем делимость того же выражения и на 31. Заметим, что . И так как , то при некотором целом имеем равенство , значит, , откуда и следует делимость исходного выражения на .

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