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

Как решать подобные задачи? Рассмотрим, какие остатки дают первые несколько степеней.

Легко видеть, что следующая степень снова сравнима с 2 по модулю 9. Итак, впервые некоторый остаток повторился. На самом деле после этого все остатки зацикливаются, и после 2 снова будет 4, 8, 7, 5, 1, 2, и т. д. Почему так происходит? Дело в том, что следующий остаток однозначно определяется предыдущим. Значит, если ранее после остатка 2 шел остаток 4, то и сейчас после 2 мы получим остаток 4.

Тем самым мы получили цикл остатков: 2, 4, 8, 7, 5, 1. Поэтому достаточно посчитать, какой номер будет у числа 1000 в данном цикле. А для этого достаточно заметить, что, раз цикл имеет длину 6, то все зависит от того, какой остаток дает число 1000 при делении на 6. Нетрудно посчитать, что этот остаток равен 4. Значит, число 1000 будет четвертым по номеру в этом цикле, таким образом, дает остаток 7 при делении на 9.

Ответ

Искомый остаток равен 7.