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

Человек, который не публиковался

Пьер де Ферма (1607–1665) — советник тулузского парламента, то есть судья; математикой занимался как частное лицо и почти ничего не печатал. Его наследие — письма (Мерсенну, Френиклю, Паскалю, Каркави, Дигби) и заметки на полях книг. Первое собрание сочинений издал сын Самюэль в 1670 году, через пять лет после смерти отца.

Отсюда особенность, из-за которой Ферма — самая раздражающая фигура в этой линии: он формулирует десятки верных утверждений, сообщает, что доказательство у него есть, и почти никогда его не приводит. Проверять за ним пришлось Эйлеру, Лагранжу, Гауссу — и на это ушло полтора столетия.

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

Письмо Бернару Френиклю де Бесси от 18 октября 1640 года:

Всякое простое число неизменно измеряет одну из степеней минус единица любой прогрессии… И я послал бы Вам доказательство, если бы не боялся быть слишком длинным.

В современной записи:

$$a^{p-1}\equiv 1 \pmod p\qquad (p \text{ простое},\ p\nmid a),$$

или в форме, верной без оговорок: $a^{p}\equiv a\pmod p$.

Доказательство перестановкой вычетов. Рассмотрим числа $a,2a,\dots,(p-1)a$ по модулю $p$. Все они ненулевые (так как $p\nmid a$) и попарно различны: если $ia\equiv ja$, то $p\mid(i-j)a$, значит $p\mid i-j$, что при $1\leqslant i,j\leqslant p-1$ даёт $i=j$. Значит, это те же самые $1,2,\dots,p-1$, только переставленные. Перемножим:

$$a^{p-1}(p-1)!\equiv(p-1)!\pmod p,$$

и, сократив на $(p-1)!$ (оно взаимно просто с $p$), получаем требуемое. $\blacksquare$

Доказательство ожерельями — комбинаторное и очень наглядное. Составим все ожерелья из $p$ бусин $a$ цветов; всего последовательностей $a^{p}$. Одноцветных — ровно $a$. Остальные разбиваются на группы по $p$ штук: циклический сдвиг переводит их друг в друга, и все $p$ сдвигов различны (иначе период делил бы $p$, а $p$ простое). Значит, $p\mid a^{p}-a$. $\blacksquare$

Первое опубликованное доказательство дал Эйлер в 1736 году — через 96 лет.

Обобщение Эйлера (1763). Для произвольного модуля:

$$a^{\varphi(n)}\equiv1\pmod n\qquad (\gcd(a,n)=1),$$

где $\varphi(n)$ — количество чисел от 1 до $n$, взаимно простых с $n$. Для простого $n=p$ имеем $\varphi(p)=p-1$, и получается теорема Ферма.

Почему на этом стоит криптография

Возьмём два больших простых $p$ и $q$, положим $n=pq$; тогда $\varphi(n)=(p-1)(q-1)$. Выберем $e$, взаимно простое с $\varphi(n)$, и найдём $d$ из условия $ed\equiv1\pmod{\varphi(n)}$ — это делается алгоритмом куттака. Тогда для любого сообщения $m$

$$(m^{e})^{d}=m^{ed}=m^{1+k\varphi(n)}=m\cdot\left(m^{\varphi(n)}\right)^{k}\equiv m \pmod n .$$

Зашифровать — возвести в степень $e$, расшифровать — в степень $d$. Публикуется пара $(n,e)$; чтобы вычислить $d$, нужно знать $\varphi(n)$, а для этого — разложить $n$ на множители. Это и есть RSA (точка о нём стоит в дискретной линии). Вся конструкция — теорема Эйлера, то есть теорема Ферма 1640 года.

Осторожно: обратное неверно

Соблазнительно проверять простоту так: если $2^{n-1}\equiv1\pmod n$, объявить $n$ простым. Это тест Ферма, и он ошибается.

Наименьший контрпример: $n=341=11\cdot31$, для которого $2^{340}\equiv1\pmod{341}$. Такие числа называются псевдопростыми по основанию 2.

Хуже того, есть числа Кармайкла — составные $n$, для которых $a^{n-1}\equiv1$ при всех взаимно простых с $n$ основаниях; их не отсеет никакая смена основания. Наименьшее:

$$561=3\cdot11\cdot17 .$$

Критерий Корсельта: $n$ — число Кармайкла тогда и только тогда, когда $n$ свободно от квадратов и $(p-1)\mid(n-1)$ для каждого простого делителя $p$. Проверим для 561: делители 3, 11, 17; $n-1=560$; и $2\mid560$, $10\mid560$, $16\mid560$. $\checkmark$

Что чисел Кармайкла бесконечно много, доказали только в 1994 году (Алфорд, Гранвилл, Померанс). Практические тесты (Миллера — Рабина) устроены хитрее и обходят эту ловушку.

Что ещё было в 1640 году

Рождественская теорема. В письме Мерсенну от 25 декабря 1640 года: простое вида $4k+1$ представимо суммой двух квадратов, и притом единственным способом; простое вида $4k+3$ — не представимо никак. Например $13=4+9$, $29=25+4$, а $7$, $11$, $19$ — нельзя. Доказал Эйлер после семи лет попыток.

Метод бесконечного спуска. Собственное изобретение Ферма и, по его словам, главное: если из решения в натуральных числах строится меньшее решение, то решений нет вовсе — натуральный ряд не допускает бесконечного убывания. Этим методом он доказал единственный известный нам его результат по Великой теореме — случай $n=4$: уравнение $x^{4}+y^{4}=z^{4}$ решений не имеет.

Заметка на полях. Примерно в те же годы на полях «Арифметики» Диофанта появляется знаменитая фраза о том, что разложить куб на два куба невозможно, и что доказательство удивительное, а поля узки. Что за этим стояло, мы не узнаем; современный консенсус — что доказательства у него не было, а был, вероятно, спуск для четвёртой степени, ошибочно обобщённый. Закрыто это будет через 357 лет.

Задача. Найдите остаток от деления $3^{100}$ на 7 и $7^{222}$ на 11 — не считая степеней.
(Ответ: по малой теореме $3^{6}\equiv1\pmod 7$; $100=6\cdot16+4$, значит $3^{100}\equiv3^{4}=81\equiv4$. Для второго: $7^{10}\equiv1\pmod{11}$, $222=10\cdot22+2$, значит $7^{222}\equiv49\equiv5$.)

Следующая точка: Петербург — где за Ферма всё доказывают и попутно выясняют, что о простых числах можно узнавать из бесконечных рядов.