33 = -15 (mod 8).
Возникает естественный вопрос: в каком случае можно в сравнении (7.3.7) сократить общий множитель с и получить при этом верное сравнение
a ≡ b (mod m )?
Именно здесь сравнения отличаются от уравнений. Например, верно, что
22 ≡ -2 (mod 8),
но сокращение на множитель 2 дало бы сравнение
11 ≡ -1 (mod 8),
которое неверно.
В одном важном случае сокращение допустимо:
если ас ≡ bc (mod m), то a ≡ b (mod m) при условии, что числа m и с взаимно просты.
Доказательство. Первое сравнение означает, что
ас — bc = ( а — b ) с = mk .
Если D ( m, с ) = 1, то отсюда следует, что а — b делится на m в соответствии с результатом, доказанным в § 2 главы 4.
Пример. В сравнении
4 ≡ 48 (mod 11)
мы можем сократить на множитель 4, так как D (11, 4) = 1. Это дает
1 ≡ 12 (mod 11).
Система задач 7.3.
1. Придумайте еще несколько примеров на использование изложенных правил действий со сравнениями.
§ 4. Возведение сравнений в степень
Предположим вновь, что имеется сравнение
a ≡ b (mod m ).
Как мы только что видели, можно умножить это сравнение на себя, получив
а 2≡ b 2(mod m ).
Вообще можно, умножив это сравнение на себя нужное количество раз, получить
a n ≡ b n (mod m )
для любого целого положительного числа m .
Пример. Из сравнения
8 ≡ -3 (mod 11)
после возведения в квадрат следует сравнение
64 ≡ 9 (mod 11),
а после возведения в куб получаем сравнение
512 ≡ -27 (mod 11).
Многие результаты теории сравнений связаны с остатками высоких степеней чисел, поэтому покажем, как можно продолжить процесс возведения в степень. Предположим, например, что мы хотим найти остаток сравнения
3 89(mod 7).
Одним из путей для выполнения этого является повторное возведение в квадрат. Мы находим:
9 = 3 2≡ 2 (mod 7),
3 4≡ 4,
3 8≡ 16 ≡ 2,
3 64≡ 4 (mod 7).
Так как
89 = 64 + 16 + 8 + 1 = 2 6+ 2 4+ 2 3+ 1,
то отсюда следует, что
3 89= 3 64• З 16• З 8• 3 = 4 • 4 • 2 • 3 ≡ 5 (mod 7).
Таким образом, остаток (по модулю 7) есть 5, или, говоря другими словами, в соответствии с изложенным в § 2, последняя цифра числа З 89, записанного в системе счисления при основании 7, равна 5.
В действительности, для того чтобы найти этот остаток, мы записали показатель степени
89 = 2 6+ 2 4+ 2 3+ 1 = (1, 0, 1, 1, 0, 0, 1)
в двоичной системе счисления. Повторным возведением в квадрат мы нашли остатки (по модулю 7) тех степеней числа 89, которые сами являются степенями числа 2:
1, 2, 4, 8, 16, 32, 64.
Соответствующий метод можно использовать для любых других оснований. Однако в частном случае бывает возможность упростить вычисление, если заметить особенности этого случая. Например, в случае, разобранном выше, мы можем отметить, что
3 3≡ -1 (mod 7),
З 6≡ 1 (mod 7),
откуда заключаем, что
3 84= (3 6) 14≡ 1 (mod7).
Поэтому
3 89= 3 84 • 3 3 • 3 2≡ 1 • (-1) • 2 = -2 ≡ 5 (mod 7),
как и раньше.
В качестве другой иллюстрации сказанного можно рассмотреть числа Ферма, с которыми мы познакомились в § 3 гл. 2:
F n = 2 2ⁿ+1.
Первые пять чисел Ферма таковы:
F 0= 3, F 1= 5, F 2= 17, F 3= 257, F 4= 65537.
Отсюда можно высказать предположение:
десятичная запись всех чисел Ферма, за исключением F 0 и F 1 оканчивается цифрой 7.
Докажем с помощью сравнений, что это действительно так. Очевидно, что оно равносильно утверждению, что числа
2 2ⁿ, n = 2, 3…
оканчиваются цифрой 6. Это можно доказать по индукции. Заметим, что
2 2²= 16 ≡ 6 (mod 10),
2 2³= 256 ≡ 6 (mod 10),
2 2ˆ 4 = 65536 ≡ 6 (mod 10),
Более того, если мы возводим в квадрат число 2 2ˆ k , то результатом будет число

Предположим, что для некоторого значения t
;
возводя в квадрат это сравнение, мы находим, что
,
что и требовалось.
Из алгебры мы знаем правила возведения бинома в степень:
( x + у ) 1= х + у ,
( х + у ) 2= x 2+ 2 xy + y 2,
( x + y ) 3= х 3+ З x 2 y + З ху 2+ у 3,
( x + у ) 4= х 4+ 4 х 3 у + 6 х 2 у 2+ 4 ху 3+ у 4(7.5.1)
Читать дальше