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

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

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

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

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

(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) как сравнение по модулю р, то можно сделать вывод, что для любых целых чисел х и у и простого р