k и l — целые числа. Сложим уравнения (7.3.2).
В результате получаем
а + с = b + d + m (k + l),
что можем записать как
а + с≡b + d (mod m); (7.3.3)
другими словами, два сравнения можно складывать. Таким же образом можно показать, что одно сравнение можно вычитать из другого, т. е. что
a — c≡b — d (mod m). (7.3.4)
Пример.
11 ≡ —5 (mod 8) и 7 = — 9 (mod 8). (7.3.5)
Складывая их, получаем
18 ≡ — 14 (mod 8),
а вычитая,
4 ≡ 4 (mod 8).
Оба эти сравнения справедливы.
Можно также перемножить два сравнения. Из (7.3.1) и (7.3.2) следует, что
ac = bd + m(kd + bl + mkl),
таким образом,
ас≡bd (mod m). (7.3.6)
Пример. Когда два сравнения из (7.3.5) перемножены, получается
77 = 45 (mod 8).
Сравнение a≡b (mod m) может быть умножено на любое целое число с, при этом получаем
ас≡bc (mod m). (7.3.7)
Это можно рассматривать как частный случай умножения сравнений (7.3.6) при с = d. Его можно также рассматривать как прямое следствие из определения сравнения.
Пример. Когда первое сравнение из (7.3.5) умножается на 3, получаем, что
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≡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
;
возводя в квадрат это сравнение, мы находим, что
,
что и требовалось.
§ 5. Теорема Ферма
Из алгебры мы знаем правила возведения бинома в степень:
(x + у)1 = х + у,
(х + у)2 = x2 + 2xy + y2,
(x + y)3 = х3 + Зx2y + Зху2 + у3,
(x + у)4 = х4 + 4х3у + 6х2у2 + 4ху3 + у4 (7.5.1)
и вообще
(х + у)p = хр + Cp1xp-1y + Ср2хр-2y2 +… + ур. (7.5.2)
Здесь первый и последний коэффициенты равны единице. Средними биномиальными коэффициентами являются
Cp1 = p/1, Ср2 = p(p-1)/(1 2), Ср3 = p(p-1)(p-2)/(1 • 2 • 3)… (7.5.3)
и вообще
Срr= p(p-1)(p-2)… (p — r + 1)/(1 2… r), (7.5.4)
Так как эти коэффициенты получаются в результате последовательного умножения на бином (х + у), то ясно, что они являются целыми числами.
С этого момента будем считать, что р — простое число. Чтобы записать эти коэффициенты в целочисленном виде, необходимо сократить все общие множители знаменателя
1 • 2 • 3 •… • r
и числителя
p(p-1)(p-2)… (p — r + 1)
Однако знаменатель не содержит простого множителя р, поэтому после сокращения число р останется множителем в числителе. Мы делаем вывод.
Все биномиальные коэффициенты (кроме первого и последнего) в выражении (7.5.2) делятся на р, если р — простое число.
Пусть теперь х и у в выражении (7.5.2) будут целыми числами. Если мы рассмотрим формулу (7.5.2) как сравнение по модулю р, то можно сделать вывод, что для любых целых чисел х и у и простого р
(х + у)p≡хр + ур (mod p). (7.5.5)
В качестве примера возьмем р = 5:
(х + у)5 = х5 + 5х4у + 10x3y2 + 10x2y3 + 5xy4 + у5.
Так как все средние коэффициенты делятся на 5, то
(х + у)5≡х5 + у5 (mod 5)
в соответствии с (7.5.5).
Из сравнения (7.5.5) можно сделать важные выводы. Применим его для случая х = у = 1. Получаем
2p = (1 + 1)p≡ 1p + 1p = 2 (mod p).
Возьмем затем х = 2, у = 1 и найдем, что
3p = (2 + 1)p≡ 2p + 1p;
теперь, используя предыдущий результат, 2p≡ 2 (mod p), получаем
2p + 1p ≡