§ 5.5. Степени

Во многих приложениях мы будем встречаться со следующей задачей: пусть — натуральные числа; найти остаток от деления на Если к очень большое, то может оказаться невозможным даже пересчитать знаки в как в примере из начала этой главы. Однако мы можем упростить эту проблему, используя арифметику остатков.

Начнем с простого примера. Предположим, что мы хотим найти остаток от деления на 7. Мы видели в предыдущем параграфе, что . Деля 135 на 6, мы найдем Полученное равенство дает следующие сравнения по модулю 7:

Значит остаток от деления на 7 равен 6.

Вычисления не всегда оказываются такими легкими. Например, какой остаток получится при делении на 31? Вычислив несколько степеней 3 по модулю 31, мы быстро найдем, что . Вместо вычисления более высоких степеней в надежде, что одна из них станет снова 1, воспользуемся уже имеющейся информацией. Так как мы получаем сравнение по модулю 31:

Мы еще не получили искомый остаток, а только степень 2, которая лежит между нами и нашей целью. Удачно, что . Так как мы находим

Но , так что остаток от деления на 31 равен 19.

Были бы вычисления легче, продолжай мы находить степени 3 до тех пор, пока не встретится 1? Ответ — нет, в чем

Вы сами можете убедиться, попытавшись найти наименьшее натуральное для которого

Предположим теперь, что мы хотим найти остаток от деления на 16. В этом случае бесполезно пытаться отыскать наименьшую степень 6, сравнимую с 1 по модулю 16: ее просто нет. Действительно,

откуда

Эти примеры иллюстрируют некоторые трюки, используемые для облегчения подсчета вычетов степеней по модулю Другие приемы появятся в последующих главах. Конечно, компьютеру не нужны никакие трюки. Это не говорит о том, что компьютер не использует арифметику остатков для таких вычислений; на самом деле, он ее использует. Быстрый алгоритм, вычисляющий степени по модулю можно найти в § П.2 приложения. Его можно использовать для доказательства делимости на достижение, которое раньше казалось невыполнимой задачей.