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

Частные случаи утверждения были известны задолго до Ферма. Так называемая китайская гипотеза — предположение, что ${\displaystyle n}$ является простым тогда и только тогда, когда ${\displaystyle 2^{n}-2}$ делится на ${\displaystyle n}$, — по легенде восходила к древнекитайской математике; в действительности приписывание этого результата математикам эпохи Конфуция основано на ошибке толкования, допущенной в XIX веке^[5][6]. Прямая часть этой гипотезы — частный случай малой теоремы Ферма при ${\displaystyle a=2}$.

Пьер Ферма сформулировал исходное утверждение теоремы в письме от 18 октября 1640 года к французскому математику Бернару Френиклю де Бесси^[7]:

В качестве примера Ферма приводит прогрессию 3, 9, 27, 81, 243, 729… и простое число 13. Число 13 делит 27 − 1 = 26 (показатель степени для 27 равен 3, а 3 делит 13 − 1 = 12), из чего следует, что 13 также делит 729 − 1 = 728 (показатель степени для 729 равен 6 и кратен 3). На современном языке Ферма фактически заметил, что порядок числа по модулю делит ${\displaystyle p-1}$: порядок тройки по модулю 13 равен трём.

Сам Ферма оставил свою теорему без доказательства, опубликовал её сын Ферма примерно в 1660 году. Первым математиком, нашедшим доказательство, был Готфрид Вильгельм Лейбниц: из его рукописей следует, что доказательство было ему известно до 1683 года. Лейбниц не знал о результате Ферма и открыл теорему независимо^[8]. Однако работа Лейбница не была опубликована, и первое печатное доказательство обнародовал Леонард Эйлер в 1736 году в статье «Theorematum quorundam ad numeros primos spectantium demonstratio»^[9]. Позднее Эйлер дал ещё несколько доказательств и в 1760 году обобщил теорему на составной модуль, придя к теореме Эйлера^[10].

В 1806 году шотландский математик Джеймс Айвори опубликовал доказательство, основанное на том, что если ${\displaystyle x}$ пробегает полную систему вычетов по модулю ${\displaystyle p}$, то для любого ${\displaystyle a,}$ не кратного ${\displaystyle p,}$ произведение ${\displaystyle ax}$ также пробегает полную систему вычетов; эта идея лежит в основе большинства современных изложений. Позднее то же рассуждение независимо переоткрыл Петер Густав Лежён Дирихле^[11].

Число

${\displaystyle q_{p}(a)={\frac {a^{p-1}-1}{p}}}$

называется частным Ферма. Русский математик Д. А. Граве предположил, что частное Ферма при ${\displaystyle a=2}$ никогда не делится на ${\displaystyle p}$, то есть что ${\displaystyle 2^{p-1}-1}$ не делится на ${\displaystyle p^{2}}$. Для простых чисел, не превышающих 1000, это действительно так, однако в 1913 году В. Мейснер обнаружил контрпример: при ${\displaystyle p=1093}$ частное Ферма делится на 1093. В 1922 году Н. Бегер нашёл второй такой случай, ${\displaystyle p=3511}$; других простых чисел с этим свойством до ${\displaystyle 10^{17}}$ не найдено. Такие числа называются простыми числами Вифериха^[12].

Следующая формулировка отличается отсутствием требования, чтобы число ${\displaystyle a}$ не делилось на ${\displaystyle p}$:

К примеру, если ${\displaystyle a=7,\;p=5}$, то ${\displaystyle 7^{5}=16\,807=5\cdot 3361+2,}$ и ${\displaystyle 7=5\cdot 1+2}$.

Эта формулировка сводится к исходной. Если ${\displaystyle a}$ делится на ${\displaystyle p}$, то ${\displaystyle a\equiv 0{\pmod {p}}}$ и ${\displaystyle a^{p}\equiv 0{\pmod {p}}}$, то есть ${\displaystyle a^{p}\equiv a{\pmod {p}}}$. Если же ${\displaystyle a}$ не делится на ${\displaystyle p}$, то сравнение ${\displaystyle a^{p}\equiv a{\pmod {p}}}$ можно сократить на ${\displaystyle a}$, поскольку ${\displaystyle a}$ обратимо по модулю ${\displaystyle p}$, и получить ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.

Обе формулировки могут быть использованы для проверки числа на простоту (см. ниже), однако основная отбраковывает больше составных чисел. Например, для ${\displaystyle n=6}$ и ${\displaystyle a=3}$ альтернативная формулировка даёт ${\displaystyle 3^{6}=729=121\cdot 6+3}$, то есть ${\displaystyle 3^{6}\equiv 3{\pmod {6}}}$, и число 6 не отбраковано. Основная же формулировка даёт ${\displaystyle 3^{5}=243=40\cdot 6+3}$, то есть ${\displaystyle 3^{5}\equiv 3\not \equiv 1{\pmod {6}}}$, и составность числа 6 обнаружена.

Малую теорему Ферма можно записать в виде тождества над конечным полем ${\displaystyle \mathbb {F} _{p}}$:

${\displaystyle x^{p}-x=\prod _{a=0}^{p-1}(x-a).}$

Действительно, каждый из ${\displaystyle p}$ элементов поля является корнем многочлена ${\displaystyle x^{p}-x}$, а степень многочлена равна ${\displaystyle p}$. Отсюда, в частности, немедленно получается теорема Вильсона: сравнивая свободные члены обеих частей, получаем ${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$ для нечётного ${\displaystyle p}$^[13].

Отображение ${\displaystyle \varphi (x)=x^{p}}$ на кольце характеристики ${\displaystyle p}$ является гомоморфизмом, называемым эндоморфизмом Фробениуса: из того, что все биномиальные коэффициенты ${\displaystyle {\tbinom {p}{k}}}$ при ${\displaystyle 0<k<p}$ делятся на ${\displaystyle p}$, следует

${\displaystyle (x+y)^{p}=x^{p}+y^{p}.}$

Малая теорема Ферма равносильна утверждению, что на простом поле ${\displaystyle \mathbb {F} _{p}}$ этот гомоморфизм является тождественным отображением.

Рассмотрим все строки длины ${\displaystyle p}$ из букв ${\displaystyle a}$-буквенного алфавита; всего их ${\displaystyle a^{p}}$. Из них ровно ${\displaystyle a}$ строк состоят из одинаковых букв. Остальные ${\displaystyle a^{p}-a}$ строк разобьём на классы, объединяя строки, получающиеся друг из друга циклическим сдвигом. Если бы некоторая строка совпала со своим сдвигом на ${\displaystyle k}$ позиций при ${\displaystyle 0<k<p}$, то её период делил бы ${\displaystyle p}$; так как ${\displaystyle p}$ простое, период равнялся бы 1, то есть строка была бы одноцветной, что исключено. Значит, каждый класс содержит ровно ${\displaystyle p}$ различных строк, и число ${\displaystyle a^{p}-a}$ делится на ${\displaystyle p}$. Такие классы называются ожерельями; это доказательство опубликовал в 1872 году Юлиус Петерсен^[15].

Основное обобщение получается заменой простого модуля произвольным: если ${\displaystyle a}$ и ${\displaystyle m}$ взаимно просты, то

${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}},}$

где ${\displaystyle \varphi }$ — функция Эйлера. При простом ${\displaystyle m=p}$ имеем ${\displaystyle \varphi (p)=p-1}$, и получается малая теорема Ферма.

Показатель ${\displaystyle \varphi (m)}$ не всегда наименьший из возможных. Наименьший показатель, годящийся сразу для всех оснований, даёт функция Кармайкла ${\displaystyle \lambda (m)}$: например, ${\displaystyle \varphi (8)=4}$, тогда как ${\displaystyle \lambda (8)=2}$, и действительно ${\displaystyle a^{2}\equiv 1{\pmod {8}}}$ для всех нечётных ${\displaystyle a}$. Величина ${\displaystyle \lambda (m)}$ — это экспонента группы обратимых вычетов, то есть наименьшее общее кратное порядков её элементов; в отличие от ${\displaystyle \varphi (m)}$, она не является порядком группы, поэтому теорема Кармайкла не выводится непосредственно из теоремы Лагранжа.

Следует отметить, что группа обратимых вычетов по модулю ${\displaystyle m}$ в общем случае не является циклической — так, при ${\displaystyle m=8}$ она изоморфна ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{2}}$. Поэтому теорема Эйлера выводится из теоремы Лагранжа для произвольных конечных абелевых групп, а не только для циклических^[17].

Сама теорема Эйлера допускает обобщение, уточняющее показатель для составного модуля. Если ${\displaystyle m=p_{1}^{k_{1}}\cdots p_{s}^{k_{s}}}$ — разложение на простые множители, то для любого целого ${\displaystyle a}$ справедливо сравнение^[18]

${\displaystyle a^{m}-\sum _{i}a^{m/p_{i}}+\sum _{i<j}a^{m/p_{i}p_{j}}-\cdots +(-1)^{s}a^{m/p_{1}\cdots p_{s}}\equiv 0{\pmod {m}}.}$

Например, при ${\displaystyle m=360=2^{3}\cdot 3^{2}\cdot 5}$:

${\displaystyle a^{360}-a^{180}-a^{120}-a^{72}+a^{60}+a^{36}+a^{24}-a^{12}\equiv 0{\pmod {360}}.}$

Гаусс доказал это сравнение только для простых ${\displaystyle a}$; в общем случае оно было доказано сразу несколькими математиками в 1880-е годы. Теорема является лёгким следствием теоремы Эйлера: левая часть сравнения для каждого простого делителя ${\displaystyle p_{i}}$ модуля ${\displaystyle m}$ распадается на группы слагаемых вида ${\displaystyle b^{\varphi (p_{i}^{k_{i}})\cdot t}-b^{\varphi (p_{i}^{k_{i}})\cdot t'}}$, обращающиеся в нуль по модулю ${\displaystyle p_{i}^{k_{i}}}$, как это видно на примере ${\displaystyle m=360}$.

• Если ${\displaystyle p}$ — простое число, то для любого ненулевого элемента ${\displaystyle a}$ поля ${\displaystyle \mathbb {Z} _{p}}$ выполняется равенство ${\displaystyle a^{-1}=a^{p-2}}$. Это даёт способ вычисления обратного элемента быстрым возведением в степень^[19].

• Если ${\displaystyle p}$ — простое число, отличное от 2 и 5, то число ${\displaystyle 10^{p-1}-1}$, в десятичной записи которого присутствуют только цифры ${\displaystyle 9}$, делится на ${\displaystyle p}$. Отсюда следует, что для любого целого числа ${\displaystyle N}$, не делящегося ни на 2, ни на 5, можно подобрать число, состоящее только из девяток, которое делится на ${\displaystyle N}$. Этот факт используется в теории признаков делимости и при изучении периода периодических дробей^[20].

• Малая теорема Ферма позволяет находить простые делители чисел специального вида. Всякий простой делитель числа ${\displaystyle a^{4}+a^{3}+a^{2}+a+1}$ либо равен 5, либо сравним с единицей по модулю 5; всякий простой делитель числа ${\displaystyle a^{2^{n}}+1}$ при чётном ${\displaystyle a}$ сравним с единицей по модулю ${\displaystyle 2^{n+1}}$. Последнее свойство использовал Эйлер, разложив на множители пятое число Ферма ${\displaystyle 2^{32}+1}$^[21].

• Обобщением малой теоремы Ферма на алгебраические числа является теорема, сформулированная Теодором Шёнеманом в 1839 году: пусть ${\displaystyle a_{1},\dots ,a_{d}}$ — корни нормированного многочлена ${\displaystyle f\in \mathbb {Z} [x]}$ степени d, а p — простое число. Тогда

${\displaystyle a_{1}^{p}+a_{2}^{p}+\dots +a_{d}^{p}\equiv a_{1}+\dots +a_{d}{\pmod {p}}.}$

Утверждение следует из сравнения ${\displaystyle (x_{1}+\cdots +x_{d})^{p}\equiv x_{1}^{p}+\cdots +x_{d}^{p}{\pmod {p}}}$, которое вытекает из делимости биномиальных коэффициентов ${\displaystyle {\tbinom {p}{k}}}$ на ${\displaystyle p}$ при ${\displaystyle 0<k<p}$, и обычной малой теоремы Ферма^[22].

• Теорема Эйлера также обобщается на алгебраические числа: в тех же обозначениях для любого натурального ${\displaystyle n}$ (К. СмайТ, 1986)^[23]

${\displaystyle a_{1}^{p^{n}}+\cdots +a_{d}^{p^{n}}\equiv a_{1}^{p^{n-1}}+\cdots +a_{d}^{p^{n-1}}{\pmod {p^{n}}},}$

что при ${\displaystyle n=1}$ даёт теорему Шёнемана.

• Из теоремы Смайта следует высказанное В. И. Арнольдом (2006) в качестве гипотезы утверждение о следах: для целочисленной квадратной матрицы ${\displaystyle A}$^[24]

${\displaystyle \operatorname {tr} A^{p^{n}}\equiv \operatorname {tr} A^{p^{n-1}}{\pmod {p^{n}}},}$

поскольку собственные значения матрицы ${\displaystyle A}$ — корни её характеристического многочлена, который является нормированным многочленом с целыми коэффициентами. А. В. Зарелуа распространил это сравнение на целые числа полей алгебраических чисел^[25].

• Из малой теоремы Ферма следует теорема Вильсона: натуральное число ${\displaystyle p>1}$ является простым тогда и только тогда, когда ${\displaystyle (p-1)!+1}$ делится на ${\displaystyle p}$.

Малая теорема Ферма может быть использована для тестирования числа на простоту: если ${\displaystyle a^{p}-a}$ не делится на ${\displaystyle p}$, то ${\displaystyle p}$ — составное число. Однако обращение малой теоремы Ферма в общем случае неверно: если ${\displaystyle a}$ и ${\displaystyle p}$ — взаимно простые числа и ${\displaystyle a^{p-1}-1}$ делится на ${\displaystyle p}$, то число ${\displaystyle p}$ может быть как простым, так и составным. В последнем случае оно называется псевдопростым Ферма по основанию ${\displaystyle a}$Назаренко Ю. Л. Сравнение эффективности методов определения простоты числа программно-вычислительными средствами // European science. — 2017. — № 8 (30)..

К примеру, китайская гипотеза утверждает, что ${\displaystyle p}$ является простым числом тогда и только тогда, когда ${\displaystyle 2^{p}\equiv 2{\pmod {p}}}$^[5]. Прямое утверждение — частный случай малой теоремы Ферма, обратное же ложно: Пьер Фредерик Саррюс в 1819 году нашёл, что ${\displaystyle 2^{340}-1}$ делится на ${\displaystyle 341}$ (это следует из того, что ${\displaystyle 2^{340}-1}$ делится на ${\displaystyle 2^{10}-1=1023=3\cdot 341}$). Однако ${\displaystyle 341}$ — составное число: ${\displaystyle 341=11\cdot 31}$. Таким образом, ${\displaystyle 341}$ — наименьшее псевдопростое число по основанию 2; такие числа называют также числами Саррюса или числами Пуле^[27].

Смена основания не спасает положения: существуют числа ${\displaystyle n}$, псевдопростые по любому основанию ${\displaystyle a}$, взаимно простому с ${\displaystyle n}$. Это числа Кармайкла; наименьшее из них — ${\displaystyle 561=3\cdot 11\cdot 17}$, за ним следуют 1105, 1729, 2465, 2821. При этом всякое число Кармайкла является произведением не менее трёх различных нечётных простых чисел. В 1994 году было доказано, что чисел Кармайкла бесконечно много.

Ввиду того, что обращение малой теоремы Ферма неверно, выполнение её условия не гарантирует, что ${\displaystyle p}$ — простое число. Тем не менее малая теорема Ферма лежит в основе теста Ферма на простоту^[28]. Тест Ферма является вероятностным: если сравнение не выполняется, число точно составное, а если выполняется — число простое с некоторой вероятностью. Среди других вероятностных методов — тест Соловея — Штрассена и тест Миллера — Рабина; последний усиливает тест Ферма, дополнительно проверяя отсутствие нетривиальных квадратных корней из единицы^[29]. Существует и детерминированный полиномиальный алгоритм — Тест Агравала — Каяла — Саксены.

Справедливы также следующие два утверждения. Если число ${\displaystyle n}$ удовлетворяет сравнению ${\displaystyle 2^{n-1}\equiv 1{\pmod {n}}}$, то ему удовлетворяет и число ${\displaystyle 2^{n}-1}$; отсюда следует, что псевдопростых по основанию 2 бесконечно много. Для любого простого числа ${\displaystyle n}$ и любого ${\displaystyle a>2}$ такого, что ${\displaystyle \gcd(a^{2}-1,\;n)=1}$, значение ${\displaystyle {\tfrac {a^{2n}-1}{a^{2}-1}}}$ является псевдопростым числом Ферма по основанию ${\displaystyle a}$^[30].

Малая теорема Ферма используется при доказательстве корректности алгоритма шифрования RSA. В этой криптосистеме выбираются два больших простых числа ${\displaystyle p}$ и ${\displaystyle q}$, полагается ${\displaystyle N=pq}$, а показатели ${\displaystyle e}$ и ${\displaystyle d}$ подбираются так, что ${\displaystyle ed\equiv 1{\pmod {\varphi (N)}}}$. Шифрование и расшифрование задаются формулами ${\displaystyle c=m^{e}{\bmod {N}}}$ и ${\displaystyle m=c^{d}{\bmod {N}}}$.

Корректность означает, что ${\displaystyle m^{ed}\equiv m{\pmod {N}}}$. Так как ${\displaystyle ed=1+k\varphi (N)}$, по малой теореме Ферма для каждого из простых модулей выполняется ${\displaystyle m^{ed}\equiv m{\pmod {p}}}$ и ${\displaystyle m^{ed}\equiv m{\pmod {q}}}$ — в том числе в случаях, когда ${\displaystyle m}$ делится на ${\displaystyle p}$ или на ${\displaystyle q}$. По китайской теореме об остатках отсюда следует ${\displaystyle m^{ed}\equiv m{\pmod {N}}}$.

Малая теорема Ферма применяется в криптографии и напрямую: на её основе строится протокол Диффи — Хеллмана и схема Эль-Гамаля, стойкость которых опирается на трудность дискретного логарифмирования в группе вычетов^[31].

• Вычисление обратных элементов. Равенство ${\displaystyle a^{-1}=a^{p-2}}$ в ${\displaystyle \mathbb {Z} _{p}}$ позволяет находить обратный элемент за ${\displaystyle O(\log p)}$ умножений, что применяется в алгоритмах компьютерной алгебры и при работе с конечными полями.

• Помехоустойчивое кодирование. Свойства мультипликативной группы конечного поля, следующие из малой теоремы Ферма, лежат в основе построения кодов БЧХ и кодов Рида — Соломона^[32].

• Проверка вычислений и признаки делимости. Классические признаки делимости на 7, 11 и 13 объясняются тем, что ${\displaystyle 10^{6}\equiv 1}$ по каждому из этих модулей.