Приглашение в теорию чисел - страница 30
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
возводя в квадрат это сравнение, мы находим, что
что и требовалось.
§ 5. Теорема Ферма
Из алгебры мы знаем правила возведения бинома в степень:
(x + у)>1 = х + у,
(х + у)>2 = x>2 + 2xy + y>2,
(x + y)>3 = х>3 + Зx>2y + Зху>2 + у>3,
(x + у)>4 = х>4 + 4х>3у + 6х>2у>2 + 4ху>3 + у>4 (7.5.1)
и вообще
(х + у)>p = х>р + C>p>1x>p>-1y + С>р>2х>р>-2y>2 +… + у>р. (7.5.2)
Здесь первый и последний коэффициенты равны единице. Средними биномиальными коэффициентами являются
C>p>1 = 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у + 10x>3y>2 + 10x>2y>3 + 5xy>4 + у>5.
Так как все средние коэффициенты делятся на 5, то
(х + у)>5 ≡ х>5 + у>5 (mod 5)
в соответствии с (7.5.5).
Из сравнения (7.5.5) можно сделать важные выводы. Применим его для случая х = у = 1. Получаем
2>p = (1 + 1)>p ≡ 1>p + 1>p = 2 (mod p).
Возьмем затем х = 2, у = 1 и найдем, что
3>p = (2 + 1)>p ≡ 2>p + 1>p;
теперь, используя предыдущий результат, 2>p ≡ 2 (mod p), получаем
2>p + 1>p ≡ 2 + 1 ≡ (mod p).
Итак, 3>p ≡ 3 (mod p). Далее для х = 3, у = 1 получаем
4>p ≡ 4 (mod p).
Используя этот процесс, можно доказать по индукции, что а>p ≡ a (mod p) для всех значений числа
а = 0, 1…. р -1. (7.5.6)
Случаи a = 0 и а = 1 очевидны. Так как каждое число сравнимо (mod р) с одним из остатков, записанных в (7.5.6), мы делаем вывод:
для любого целого числа а и любого простого числа р
a>p ≡ a (mod p). (7.5.7)
Это утверждение обычно называют теоремой Ферма, хотя некоторые авторы называют ее малой теоремой Ферма, чтобы отличить от последней теоремы Ферма, или гипотезы Ферма, о которой мы упоминали в § 3 главы 5.
Пример. Для р = 13 и а = 2 мы находим: 13 = 8+ 4 + 1, т. е. 2>13 = 2>8+4+1 = 2>8 2>4 • 2>1. Так как 2>4 = 16 ≡ 3 (mod 13), 2>8 ≡ 9(mod 13), то
2>13 = 2>8 • 2>4 • 2 ≡ 9 • 3 • 2 ≡ 2 (mod 13),
как и утверждает теорема Ферма.
В соответствии с правилом сокращения для сравнений, сформулированном в конце § 3, мы можем сократить общий множитель а в обеих частях записи теоремы Ферма (7.5.7) при условии, что число а взаимно просто с числом р, являющимся модулем сравнения. Это дает следующий результат:
если а является целым числом, не делящимся на простое число р, то
a>p>-1 ≡ 1 (mod p). (7.5.8)
Этот результат также называют теоремой Ферма.
Пример. Когда а = 7, р = 19, мы находим, что
7>2 = 49 ≡ 11 (mod 19)
7>4 ≡ 121 ≡ 7 (mod 19),
7>8 ≡ 49 ≡ 11 (mod 19),