Приглашение в теорию чисел

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

;

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

,

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

§ 5. Теорема Ферма

Из алгебры мы знаем правила возведения бинома в степень:

(x + у)¹ = х + у,

(х + у)² = x² + 2xy + y²,

(x + y)³ = х³ + Зx²y + Зху² + у³,

(x + у)⁴ = х⁴ + 4х³у + 6х²у² + 4ху³ + у⁴ (7.5.1)

и вообще

(х + у)^p = х^р + C_p¹x^p-1y + С_р²х^р-2y² +… + у^р. (7.5.2)

Здесь первый и последний коэффициенты равны единице. Средними биномиальными коэффициентами являются

C_p¹ = p/1, С_р² = p(p-1)/(1  2), С_р³ = 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х⁴у + 10x³y² + 10x²y³ + 5xy⁴ + у⁵.

Так как все средние коэффициенты делятся на 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¹³ = 2⁸⁺⁴⁺¹ = 2⁸  2⁴ • 2¹. Так как 2⁴ = 16 ≡ 3 (mod 13), 2⁸ ≡ 9(mod 13), то

2¹³ = 2⁸ • 2⁴ • 2 ≡ 9 • 3 • 2 ≡ 2 (mod 13),

как и утверждает теорема Ферма.

В соответствии с правилом сокращения для сравнений, сформулированном в конце § 3, мы можем сократить общий множитель а в обеих частях записи теоремы Ферма (7.5.7) при условии, что число а взаимно просто с числом р, являющимся модулем сравнения. Это дает следующий результат:

если а является целым числом, не делящимся на простое число р, то

a^p-1 ≡ 1 (mod p). (7.5.8)

Этот результат также называют теоремой Ферма.

Пример. Когда а = 7, р = 19, мы находим, что

7² = 49 ≡ 11 (mod 19)

7⁴ ≡ 121 ≡ 7 (mod 19),

7⁸ ≡ 49 ≡ 11 (mod 19),

7¹⁶ ≡ 121 ≡ 7 (mod 19),

и это дает

a^p-1 = 7¹⁸ = 7¹⁶ • 7² ≡ 7 • 11 ≡ 1 (mod 19),

что соответствует утверждению (7.5.8).

В качестве приложения теоремы Ферма вновь рассмотрим треугольники Пифагора, обсужденные в гл. 5 и докажем следующее утверждение:

произведение длин сторон треугольника Пифагора делится на 60.

Доказательство. Очевидно, достаточно доказать это для простейших треугольников. В соответствии с формулой (5.2.7), это произведение есть

Р = 2mn (m² — n²) (m² + n²) = 2mn (m⁴ — n⁴).

Число Р делится на 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 следует, что m² ≡ 1 (mod 3) и n² ≡ 1 (mod 3), так что

m² — n² ≡ 1 – 1 = 0 (mod 3).

Аналогично, число Р делится на 5. Это очевидно, если m или n делится на 5. Если ни одно из них не делится на 5, то вновь по теореме Ферма (7.5.8) получаем

m⁴ — n⁴ ≡ 1 – 1 = 0 (mod 5).

ГЛАВА 8 НЕКОТОРЫЕ ПРИМЕНЕНИЯ СРАВНЕНИЙ

§ 1. Проверка вычислений