Processing math: 100%

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

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

История


 Пьер Ферма сформулировал исходное утверждение теоремы к 1640 году. «Меняозарило ярким светом», — писал Ферма, впервые сообщая об этом своёмоткрытии в письме (1640). Интересно, что данная фраза — «mi pardi 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 PrimosSpectantium 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] степени , а  — простое число. Тогда ap1+ap2++apda1++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.