§ 4. Возведение сравнений в степень

§ 4. Возведение сравнений в степень

Предположим вновь, что имеется сравнение

a ? b (mod m).

Как мы только что видели, можно умножить это сравнение на себя, получив

а2 ? b2 (mod m).

Вообще можно, умножив это сравнение на себя нужное количество раз, получить

an ? bn (mod m)

для любого целого положительного числа m.

Пример. Из сравнения

8 ? -3 (mod 11)

после возведения в квадрат следует сравнение

64 ? 9 (mod 11),

а после возведения в куб получаем сравнение

512 ? -27 (mod 11).

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

389 (mod 7).

Одним из путей для выполнения этого является повторное возведение в квадрат. Мы находим:

9 = 32 ? 2 (mod 7),

34 ? 4,

38 ? 16 ? 2,

364 ? 4 (mod 7).

Так как

89 = 64 + 16 + 8 + 1 = 26 + 24 + 23 + 1,

то отсюда следует, что

389 = 364 • З16 • З8 • 3 = 4 • 4 • 2 • 3 ? 5 (mod 7).

Таким образом, остаток (по модулю 7) есть 5, или, говоря другими словами, в соответствии с изложенным в § 2, последняя цифра числа З89, записанного в системе счисления при основании 7, равна 5.

В действительности, для того чтобы найти этот остаток, мы записали показатель степени

89 = 26 + 24 + 23 + 1 = (1, 0, 1, 1, 0, 0, 1)

в двоичной системе счисления. Повторным возведением в квадрат мы нашли остатки (по модулю 7) тех степеней числа 89, которые сами являются степенями числа 2:

1, 2, 4, 8, 16, 32, 64.

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

33 ? -1 (mod 7),

З6 ? 1 (mod 7),

откуда заключаем, что

384 = (36)14 ? 1 (mod7).

Поэтому

389 = 384 • 33 • 32 ? 1 • (-1) • 2 = -2 ? 5 (mod 7),

как и раньше.

В качестве другой иллюстрации сказанного можно рассмотреть числа Ферма, с которыми мы познакомились в § 3 гл. 2:

Fn = 22?+1.

Первые пять чисел Ферма таковы:

F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537.

Отсюда можно высказать предположение:

десятичная запись всех чисел Ферма, за исключением F0 и F1 оканчивается цифрой 7.

Докажем с помощью сравнений, что это действительно так. Очевидно, что оно равносильно утверждению, что числа

22?, n = 2, 3…

оканчиваются цифрой 6. Это можно доказать по индукции. Заметим, что

22? = 16 ? 6 (mod 10),

22? = 256 ? 6 (mod 10),

22?4 = 65536 ? 6 (mod 10),

Более того, если мы возводим в квадрат число 22?k, то результатом будет число

Предположим, что для некоторого значения t

;

возводя в квадрат это сравнение, мы находим, что

,

что и требовалось.