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

ОРЕ О.

Первые пять чисел Ферма таковы:

F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65537.

Отсюда можно высказать предположение:

десятичная запись всех чисел Ферма, за исключением F₀ и F₁ оканчивается цифрой 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 + у)¹ = х + у,

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

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

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

и вообще

(х + у)^p = х^р + C_p¹x^{p– 1}y + С_р²х^{р– 2}y² +… + у^р. (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).