Малая теорема Ферма¶

Малая теорема Ферма — это фундаментальное утверждение в теории чисел, устанавливающее связь между простыми числами и степенями целых чисел. В наиболее распространённой формулировке теорема гласит: если \( p \) — простое число, а \( a \) — целое число, не делящееся на \( p \), то \( a^{p-1} - 1 \) делится на \( p \). Эквивалентная формулировка: для любого целого \( a \) и простого \( p \) число \( a^p - a \) делится на \( p \). Теорема является частным случаем более общей теоремы Эйлера и лежит в основе многих криптографических алгоритмов, в частности RSA.

¶История

Малая теорема Ферма была впервые сформулирована французским математиком Пьером де Ферма (1601—1665) в письме к его корреспонденту, вероятно, в 1640 году. Ферма, как и во многих других своих работах, не привёл доказательства, ограничившись утверждением, что он нашёл его. Первое опубликованное доказательство принадлежит Готфриду Вильгельму Лейбницу (1646—1716), который, однако, не опубликовал его при жизни. Независимо от Лейбница, доказательство было опубликовано Леонардом Эйлером (1707—1783) в 1736 году. Эйлер же в 1763 году обобщил теорему на случай, когда модуль не обязательно прост, но взаимно прост с основанием (теорема Эйлера). Название «малая теорема Ферма» было введено, чтобы отличать её от «Великой (или Последней) теоремы Ферма», которая была доказана лишь в 1994 году.

¶Формулировки и обозначения

Существует несколько эквивалентных способов записи малой теоремы Ферма.

¶Основная формулировка

Пусть \( p \) — простое число, и \( a \) — целое число, не кратное \( p \) (то есть \( p \nmid a \)). Тогда:

\[ a^{p-1} \equiv 1 \pmod{p} \]

Здесь \( \equiv \pmod{p} \) означает, что левая и правая части сравнения дают одинаковый остаток при делении на \( p \). Другими словами, \( a^{p-1} - 1 \) делится на \( p \).

¶Обобщённая формулировка

Для любого целого числа \( a \) и простого \( p \) справедливо:

\[ a^p \equiv a \pmod{p} \]

Эта формулировка не требует условия, что \( a \) не делится на \( p \). Если \( p \mid a \), то обе части сравнения равны 0 по модулю \( p \), и утверждение тривиально. Если же \( p \nmid a \), то, разделив обе части на \( a \) (что возможно, так как \( a \) обратим по модулю \( p \)), получаем первую формулировку.

¶Пример

Пусть \( p = 7 \), \( a = 2 \). Тогда \( 2^{7-1} = 2^6 = 64 \). \( 64 \div 7 = 9 \) и остаток \( 1 \). Действительно, \( 64 \equiv 1 \pmod{7} \). Для обобщённой формулировки: \( 2^7 = 128 \), \( 128 \div 7 = 18 \) и остаток \( 2 \), то есть \( 128 \equiv 2 \pmod{7} \).

¶Доказательство

Существует несколько классических доказательств малой теоремы Ферма.

¶Доказательство с использованием теории групп

Рассмотрим мультипликативную группу \( (\mathbb{Z}/p\mathbb{Z})^\times \) ненулевых вычетов по модулю \( p \). Её порядок равен \( p-1 \). По теореме Лагранжа, порядок любого элемента группы делит порядок группы. Следовательно, для любого элемента \( a \) (не равного 0 по модулю \( p \)) выполняется \( a^{p-1} = 1 \) в группе, что и есть утверждение теоремы.

¶Доказательство с использованием бинома Ньютона

Рассмотрим \( (a+1)^p \). По биному Ньютона:

\[ (a+1)^p = \sum_{k=0}^{p} \binom{p}{k} a^{p-k} \cdot 1^k \]

Все биномиальные коэффициенты \( \binom{p}{k} \) для \( 1 \le k \le p-1 \) кратны \( p \), так как \( p \) — простое число, и в числителе \( p! \) есть множитель \( p \), а в знаменателе его нет. Таким образом, по модулю \( p \) все эти слагаемые обращаются в ноль, и остаётся:

\[ (a+1)^p \equiv a^p + 1 \pmod{p} \]

Далее, используя индукцию по \( a \), можно показать, что \( a^p \equiv a \pmod{p} \) для всех целых \( a \). База индукции: \( 0^p \equiv 0 \) и \( 1^p \equiv 1 \). Шаг индукции следует из полученного выше сравнения.

¶Доказательство с использованием комбинаторики

Рассмотрим \( a \) различных цветов и \( p \) бусин. Количество различных ожерелий (с учётом циклических сдвигов) из \( p \) бусин, где каждая бусина может быть любого из \( a \) цветов, равно \( a^p \). Если ожерелье состоит из бусин одного цвета, то оно не меняется при циклическом сдвиге. Таких ожерелий ровно \( a \) (по одному на каждый цвет). Все остальные \( a^p - a \) ожерелий при циклическом сдвиге дают ровно \( p \) различных вариантов, так как \( p \) — простое число, и длина периода не может быть меньше \( p \). Следовательно, \( a^p - a \) делится на \( p \).

¶Следствия и обобщения

¶Теорема Эйлера

Наиболее известное обобщение малой теоремы Ферма — теорема Эйлера: для любых взаимно простых чисел \( a \) и \( n \) выполняется:

\[ a^{\varphi(n)} \equiv 1 \pmod{n} \]

где \( \varphi(n) \) — функция Эйлера, равная количеству чисел, меньших \( n \) и взаимно простых с ним. Если \( n = p \) — простое число, то \( \varphi(p) = p-1 \), и теорема Эйлера переходит в малую теорему Ферма.

¶Тест Ферма на простоту

Малая теорема Ферма лежит в основе теста Ферма — вероятностного метода проверки числа на простоту. Если для некоторого числа \( n \) и произвольного \( a \) (1 < a < n) выполняется \( a^{n-1} \not\equiv 1 \pmod{n} \), то \( n \) — составное число. Если же сравнение выполняется, то \( n \) называется псевдопростым числом Ферма по основанию \( a \). Существуют составные числа, которые проходят тест Ферма для всех \( a \), взаимно простых с \( n \) — это числа Кармайкла. Поэтому тест Ферма не является детерминированным, но используется как быстрый предварительный этап в более сложных алгоритмах.

¶Криптография RSA

В криптосистеме RSA малая теорема Ферма (вместе с теоремой Эйлера) используется для доказательства корректности расшифрования. Если \( n = p \cdot q \), где \( p \) и \( q \) — простые числа, то для любого сообщения \( m \), взаимно простого с \( n \), выполняется \( m^{\varphi(n)} \equiv 1 \pmod{n} \). Это позволяет выбрать открытый и закрытый ключи таким образом, что \( m^{e \cdot d} \equiv m \pmod{n} \).

¶Интересные факты

Малая теорема Ферма является частным случаем теоремы Лагранжа из теории групп, что демонстрирует глубокую связь между теорией чисел и абстрактной алгеброй.
В 2016 году математик Джон Х. Конвей (1937—2020) предложил простое комбинаторное доказательство теоремы, используя игру «спринт» (sprint), что иллюстрирует её фундаментальный характер.
Теорема верна не только для целых чисел, но и для элементов любого конечного поля характеристики \( p \). В частности, в поле \( \mathbb{F}_p \) каждый элемент удовлетворяет уравнению \( x^p = x \).

¶Источники

Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.
Коблиц Н. Курс теории чисел и криптографии. — М.: Научное издательство ТВП, 1998.
Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers. — Oxford University Press, 2008.
Conway J. H., Guy R. K. The Book of Numbers. — Springer, 1996.