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

Организуем такой процесс: начнем с первой степени, на каждом шаге будем отмечать остаток числа при делении на 11 и переходить к следующей степени, домножая число на на 5. Если на нынешнем шаге мы знаем, что остаток числа равен , то есть число имеет вид , то после домножения на 5 число будет иметь вид и, соответственно, остаток, равный остатку при делении на 11 (так как оставшаяся часть и так делится на 11). То есть по факту мы просто каждый раз умножаем остаток на 5 и делим его на 11 с остатком.

Что получается?

имеет остаток 5 при делении на 11,

имеет остаток, равный остатку при делении на 11, то есть 3,

— остаток 4 (остаток при делении на 11),

— остаток 9 (остаток при делении на 11),

— остаток 1 (остаток при делении на 11),

— остаток 5 (остаток при делении на 11).

Остановимся здесь и увидим, что мы снова получили остаток 5, то есть после него будут остатки 3, 4, 9, 1, 5,..., как и с самого начала. Почему мы можем так утверждать? Заметим, что каждый остаток на очередном шаге зависит ТОЛЬКО от предыдущего остатка (больше ни от чего другого, так как мы просто каждый раз домножаем на константу 5 и берем остаток при делении на константу 11). То есть, если какой-то остаток повторился, то мы уже знаем, какие остатки будут дальше, так как мы уже ходили по этому пути.

Значит, наши остатки зациклились, а весь цикл имеет вид: 5 — 3 — 4 — 9 — 1. Теперь мы даже можем узнать точный остаток какой-то очень большой степени 5, нужно только понять на какой остаток из цикла попадает эта степень. А наш ответ: дает остатки 5, 3, 4, 9, 1.