Предположим, что для некоторого значения 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)Здесь первый и последний коэффициенты равны единице. Средними биномиальными коэффициентами являются
Cp
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у + 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 ≡ 2 + 1 ≡ (mod p).Итак, 3p
≡ 3 (mod p). Далее для х = 3, у = 1 получаем4p
≡ 4 (mod p).Используя этот процесс, можно доказать по индукции, что аp
≡ a (mod p) для всех значений числаа
= 0, 1…. р -1. (7.5.6)Случаи a
= 0 и а = 1 очевидны. Так как каждое число сравнимо (mod р) с одним из остатков, записанных в (7.5.6), мы делаем вывод:для любого целого числа а и любого простого числа р
ap
≡ a (mod p). (7.5.7)Это утверждение обычно называют теоремой Ферма
, хотя некоторые авторы называют ее малой теоремой Ферма, чтобы отличить от последней теоремы Ферма, или гипотезы Ферма, о которой мы упоминали в § 3 главы 5.Пример.
Для р = 13 и а = 2 мы находим: 13 = 8+ 4 + 1, т. е. 213 = 28+4+1 = 28 24 • 21. Так как 24 = 16 ≡ 3 (mod 13), 28 ≡ 9(mod 13), то213
= 28 • 24 • 2 ≡ 9 • 3 • 2 ≡ 2 (mod 13),как и утверждает теорема Ферма.
В соответствии с правилом сокращения для сравнений, сформулированном в конце § 3, мы можем сократить общий множитель а
в обеих частях записи теоремы Ферма (7.5.7) при условии, что число а взаимно просто с числом р, являющимся модулем сравнения. Это дает следующий результат:если а является целым числом, не делящимся на простое число р, то
ap
-1 ≡ 1 (mod p). (7.5.8)Этот результат также называют теоремой Ферма.
Пример.
Когда а = 7, р = 19, мы находим, что72
= 49 ≡ 11 (mod 19)74
≡ 121 ≡ 7 (mod 19),78
≡ 49 ≡ 11 (mod 19),716
≡ 121 ≡ 7 (mod 19),и это дает
ap
-1 = 718 = 716 • 72 ≡ 7 • 11 ≡ 1 (mod 19),что соответствует утверждению (7.5.8).
В качестве приложения теоремы Ферма вновь рассмотрим треугольники Пифагора, обсужденные в гл. 5 и докажем следующее утверждение:
произведение длин сторон треугольника Пифагора делится на 60.
Доказательство.
Очевидно, достаточно доказать это для простейших треугольников. В соответствии с формулой (5.2.7), это произведение естьР
= 2mn (m2 — n2) (m2 + n2) = 2mn (m4 — n4).Число Р
делится на 60 тогда и только тогда, когда оно делится на 4, на 3 и на 5. Так как одно из чисел m и n четно, то 2mn, а следовательно, и число Р, делится на 4. Оно делится на 3, если хотя бы одно из чисел m или n делится на 3, но если ни одно из них не делится на 3, то Р все же будет делиться на 3, так как из условий (7.5.8), а также D(m, 3) = 1 и D (n, 3) = 1 следует, что m2 ≡ 1 (mod 3) и n2 ≡ 1 (mod 3), так чтоm
2 — n2 ≡ 1 – 1 = 0 (mod 3).Аналогично, число Р
делится на 5. Это очевидно, если m или n делится на 5. Если ни одно из них не делится на 5, то вновь по теореме Ферма (7.5.8) получаемm
4 — n4 ≡ 1 – 1 = 0 (mod 5).ГЛАВА 8
НЕКОТОРЫЕ ПРИМЕНЕНИЯ СРАВНЕНИЙ
§ 1. Проверка вычислений