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

Малая теорема Ферма — теорема теории чисел, которая утверждает, что: Иначе говоря:
 К примеру, если a=2;p=7, то 26=64, и 641=63=79.
 Малая теорема Ферма является частным случаем теоремы Эйлера, которая, в свою очередь, является частным случаем теоремы Кармайкла и теоремы Лагранжа для групп для конечных циклических групп. Теорему высказал без доказательства Пьер Ферма, первое доказательство дали Леонард Эйлер и Готфрид Вильгельм Лейбниц.
 Малая теорема Ферма стала одной из главных теорем для исследований не только в теории целых чисел, но и в более широких областях.

История


 Пьер Ферма сформулировал исходное утверждение теоремы к 1640 году. «Меня озарило ярким светом», — писал Ферма, впервые сообщая об этом своём открытии в письме (1640). Интересно, что данная фраза — «mi par di veder un gran lume» написана по-итальянски, хотя всё письмо на французском языке.
 Письмо от 18 октября 1640 года Пьера Ферма к французскому математику содержало следующее положение: Каждое простое число делит [в оригинале — «измеряет»] одну из степеней любой прогрессии минус 1, для которой показатель степени является делителем данного простого числа минус 1; и после того, как была найдена первая степень, удовлетворяющая этому свойству, все числа, имеющие показатели степени, кратные показателю первой, удовлетворяют тому же свойству.
 В качестве примера Ферма приводит прогрессию 3, 9, 27, 81, 243, 729\ldots и простое число 13. 13 делит 27 − 1 (показатель степени для 27 равен 3, а 3 делит 13 − 1), из чего следует, что 13 также делит 729 − 1 (показатель степени для 729 равен 6 и кратен 3).
 Сам Ферма оставил свою теорему без доказательства. Первым математиком, нашедшим доказательство, был Готфрид Вильгельм Лейбниц, из рукописей которого следует, что доказательство ему было известно до 1683 года. Лейбниц не знал о результате Ферма и открыл теорему независимо. Однако работа Лейбница не была опубликована, и доказательство в 1736 году обнародовал Эйлер в статье Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio. Доказательство малой теоремы Ферма, основанное на том, что если x пробегает полную систему вычетов по модулю p, то для любого a:(a,p)=1 произведение ax также пробегает полную систему вычетов по модулю p, было опубликовано в 1806 году Джеймсом Айвори.
 Число ap11p называется частным Ферма. Русский математик Д. А. Граве предположил, что частное Ферма никогда не делится на p. Для простых чисел, не превышающих 1000, это действительно так, однако вскоре был обнаружен контрпример: для p=1093,a=2 частное Ферма делится на 1093.

Альтернативная формулировка


 Следующая формулировка отличается отсутствием требования, чтобы число a не делилось на p:
 К примеру, если a=7;p=5, то 75=16807=53361+2, и 7=51+2..
 Легко показать что эта формулировка сводится к изначальной. Так, если a делится на p, то a0(modp) и ap0(modp), т.е. apa(modp). Если же a не делится на p, то выражение apa(modp) эквивалентно выражению ap11(modp).

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


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



  • Если p — простое число, то в поле Zp выполняется равенство a1=ap2.
  • Если p — простое число, отличное от 2 и 5, то число 10p11, в десятичной записи которого присутствуют только цифры 9, делится на p. Отсюда следует, что для любого целого числа N, которое не делится ни на 2, ни на 5, можно подобрать число, состоящее только из девяток, которое делится на N. Этот факт используется в теории признаков делимости и периодических дробей.
  • Малая теорема Ферма позволяет находить простые делители чисел вида a4+a3+a2+a+1 и a2n+1..
  • Обобщением малой теоремы Ферма на алгебраические числа является теорема, сформулированная в 1839 году: пусть a1,,ad — корни нормированного многочлена fZ[x] степени , а  — простое число. Тогда a1p+a2p++adpa1++ad(modp).
  • Из малой теоремы Ферма следует теорема Вильсона: Натуральное число p>1 является простым тогда и только тогда, когда (p1)!+1 делится на p.

Приложения


Псевдопростые числа Ферма и тестирование на простоту


 Малая теорема Ферма может быть использована для тестирования числа на простоту: если (apa) не делится на p, то p — составное число. Однако обращение малой теоремы Ферма в общем случае неверно: если a и p — взаимно простые числа и ap11 делится на p, то число p может быть как простым, так и составным. В случае, когда p является составным, оно называется псевдопростым Ферма по основанию a.
 К примеру, утверждает, что p является простым числом тогда и только тогда, когда 2p2(modp). Здесь прямое утверждение о том, что если p простое, то 2p2(modp), является частным случаем малой теоремы Ферма. Обратное же утверждение о том, что если 2p2(modp), то p простое, есть частный случай обращения малой теоремы Ферма. Это обращение ложно: Саррус в 1820 году нашёл, что число N=234111 делится на 341, так как N делится на 2101=3341. Однако 341 — составное число: 341=1131. Таким образом, 341 — псевдопростое число по основанию 2.
 В общем случае обращение малой теоремы Ферма также не выполняется. Контрпримером в общем случае являются числа Кармайкла: это числа p, являющиеся псевдопростыми по основанию a для всех a, взаимно простых с p. Наименьшим из чисел Кармайкла является 561.
 Ввиду того, что обращение малой теоремы Ферма неверно, выполнение её условия не гарантирует что p — простое число. Тем не менее, малая теорема Ферма лежит в основе теста Ферма на простоту. Тест Ферма является вероятностным тестом на простоту: если теорема не выполняется, то число точно составное, а если выполняется — то число простое с некоторой вероятностью. Среди других вероятностных методов можно отметить: тест Соловея — Штрассена и тест Миллера — Рабина, последний в некоторой степени опирается на малую теорему Ферма. Также существует и детерминированный алгоритм: Тест Агравала — Каяла — Саксены.
 Кроме того, справедливы следующие два утверждения. Если пара (2, n) удовлетворяют сравнению an11(modn), то и пара чисел (2,2n1) также ему удовлетворяют. Для любого простого числа n и любого a \textgreater 2 такого, что (a21,n)=1, значение a2n1a21 является псевдопростым числом Ферма по основанию a.

Алгоритм RSA


 Малая теорема Ферма также используется при доказательстве корректности алгоритма шифрования RSA.