Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Ма́лая теоре́ма Ферма́ — теорема теории чисел, которая утверждает, что[1]:

Если pпростое число и aцелое число, не делящееся на p, то  a^{p-1}-1 делится на p, то есть a^{p-1}\equiv 1 \pmod p .

Иначе говоря:

~a^{p-1} сравнимо с 1 по простому модулю p.

К примеру, если a = 2; p = 7, то 2^6 = 64, и 64-1 = 63 = 7 \cdot 9.

Малая теорема Ферма является частным случаем теоремы Эйлера[2], которая, в свою очередь, является частным случаем теоремы Кармайкла и теоремы Лагранжа для групп для конечных циклических групп. Теорему высказал без доказательства Пьер Ферма, первое доказательство дали Леонард Эйлер и Готфрид Вильгельм Лейбниц.

Малая теорема Ферма стала одной из главных теорем для исследований не только в теории целых чисел, но и в более широких областях[3][4].

История[править | править вики-текст]

Пьер Ферма

Пьер Ферма сформулировал исходное утверждение теоремы к 1640 году. «Меня озарило ярким светом», - писал Ферма, впервые сообщая об этом своем открытии в письме (1640)[5]. Интересно, что данная фраза — «mi par di veder un gran lume»[6] написана по-итальянски, хотя всё письмо на французском языке.

Письмо от 18 октября 1640 года Пьера Ферма к французскому математику Бернару Френиклю (фр. Bernard Frénicle de Bessy) содержало следующее положение[7]:

Каждое простое число делит [в оригинале — «измеряет»] одну из степеней любой прогрессии минус 1, для которой показатель степени является делителем данного простого числа минус 1; и после того, как была найдена первая степень, удовлетворяющая этому свойству, все числа, имеющие показатели степени, кратные показателю первой, удовлетворяют тому же свойству.

В качестве примера Ферма приводит прогрессию 3, 9, 27, 81, 243, 729… и простое число 13. 13 делит 27 − 1 (показатель степени для 27 равен 3, а 3 делит 13 − 1), из чего следует, что 13 также делит 729 − 1 (показатель степени для 729 равен 6 и кратен 3).

Сам Ферма оставил свою теорему без доказательства. Первым математиком, нашедшим доказательство, был Готфрид Вильгельм Лейбниц, из рукописей которого следует, что доказательство ему было известно до 1683 года. Лейбниц не знал о результате Ферма и открыл теорему независимо[8]. Однако работа Лейбница не была опубликована, и доказательство в 1736 году обнародовал Эйлер в статье Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio[9]. Доказательство малой теоремы Ферма, основанное на том, что если x пробегает полную систему вычетов по модулю p, то для любого a: (a, p) = 1 произведение ax также пробегает полную систему вычетов по модулю p , было опубликовано в 1806 году Джеймсом Айвори[10].

Альтернативная формулировка[править | править вики-текст]

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

Если pпростое число и a — любое целое число, то a^p сравнимо с a по модулю p, то есть a^p\equiv a \pmod p .

К примеру, если a = 7; p = 5, то 7^5 = 16807 = 5 \cdot 3361 + 2, и 7 = 5 \cdot 1 + 2..

Легко показать что эта формулировка сводится к изначальной. Так, если a делится на p, то a\equiv 0 \pmod p и a^p\equiv 0 \pmod p, т.е. a^p\equiv a \pmod p. Если же a не делится на p, то выражение a^{p}\equiv a \pmod p эквивалентно выражению a^{p-1}\equiv 1 \pmod p [2].

Доказательства[править | править вики-текст]

Следствия и обобщения[править | править вики-текст]

  • Если p — простое число, то в поле \mathbb Z_p выполняется равенство a^{-1} = a^{p-2}[13].
  • Если p — простое число, отличное от 2 и 5, то число 10^{p-1} - 1, в десятичной записи которого присутствуют только цифры 9, делится на p. Отсюда следует, что для любого целого числа N, которое не делится ни на 2, ни на 5, можно подобрать число, состоящее только из девяток, которое делится на N. Этот факт используется в теории признаков делимости и периодических дробей[14].
  • Малая теорема Ферма позволяет находить простые делители чисел вида a^4+a^3+a^2+a+1 и a^{2^n}+1.[15].
  • Из малой теоремы Ферма следует теорема Вильсона: Натуральное число p>1 является простым тогда и только тогда, когда (p-1)!+1 делится на p.

Приложения[править | править вики-текст]

Псевдопростые числа Ферма и тестирование на простоту[править | править вики-текст]

Малая теорема Ферма может быть использована для тестирования числа на простоту: если (a^p-a) не делится на p, то p — составное число. Однако обращение малой теоремы Ферма в общем случае неверно: если a и p — взаимно простые числа и ~a^{p-1} - 1 делится на p, то число p может быть как простым, так и составным. В случае, когда p является составным, оно называется псевдопростым Ферма по основанию a.

К примеру, китайская гипотезаruen утверждает, что p является простым числом тогда и только тогда, когда 2^p \equiv 2 \pmod{p}[18]. Здесь прямое утверждение о том, что если p простое, то 2^p \equiv 2 \pmod{p}, является частным случаем малой теоремы Ферма. Обратное же утверждение о том, что если 2^p \equiv 2 \pmod{p}, то p простое, есть частный случай обращения малой теоремы Ферма. Это обращение ложно: Саррус в 1820 году нашёл, что число ~N = 2^{341-1} - 1 делится на 341, так как N делится на ~2^{10}-1=3 \cdot 341. Однако 341 — составное число: ~341 = 11 \cdot 31. Таким образом, 341 — псевдопростое число по основанию 2[19].

В общем случае обращение малой теоремы Ферма также не выполняется. Контрпримером в общем случае являются числа Кармайкла: это числа p, являющиеся псевдопростыми по основанию a для всех a, взаимно простых с p. Наименьшим из чисел Кармайкла является 561.

Ввиду того, что обращение малой теоремы Ферма неверно, выполнение её условия не гарантирует что p — простое число. Тем не менее, малая теорема Ферма лежит в основе теста Ферма на простоту[20]. Тест Ферма является вероятностным тестом на простоту: если теорема не выполняется, то число точно составное, а если выполняется — то число простое с некоторой вероятностью. Среди других вероятностных методов можно отметить: тест Соловея — Штрассена и тест Миллера — Рабина, последний в некоторой степени опирается на малую теорему Ферма[21]. Также существует и детерминированный алгоритм: Тест Агравала — Каяла — Саксены.

Кроме того, справедливы следующие два утверждения. Если пара (2, n) удовлетворяют сравнению a^{n-1}\equiv1\pmod{n}, то и пара чисел (2, 2^{n}-1) также ему удовлетворяют. Для любого простого числа n и любого a > 2 такого, что (a^{2}-1, n)=1, значение \frac{a^{2n}-1}{a^{2}-1} является псевдопростым числом Ферма по основанию a[22].

Алгоритм RSA[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Винберг, 2008, с. 43
  2. 1 2 3 Сагалович, 2014, с. 34
  3. Энциклопедия элементарной математики, Книга 1, Арифметика, Александров П. С., Маркушевич А. И., Хинчин А. Я., 1961.— С. 280
  4. З. И. Боревич, И. Р. Шафаревич. Теория чисел. — М: Наука, 1972. — 175 с.
  5. Перевод по Энциклопедический словарь юного математика. Сост. А. П. Савин. - М.: Педагогика, 1989. - 352 с. Статья: Ферма малая теорема.
  6. Fermat a Mersenne. <juin? 1640> Oeuvres de Fermat. Tome II. Paris: Tannery & Henry, 1904, pp. 195-199.
  7. Письмо от 18 октября 1640 года Пьера Ферма к французскому математику Бернару Френиклю. Архивировано из первоисточника 22 декабря 2006.
  8. 1 2 Данциг, Т. Числа — язык науки, 2008, с. 231-234
  9. David C. Marshall, Edward Odell, Michael Starbird. Number Theory Through Inquiry. — 2006. — pp. 62-63
  10. Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. Sir James Ivory (англ.) — биография в архиве MacTutor.
  11. Винберг, 2008, с. 44
  12. КВАНТ, 2000, №1, Сендеров В, Спивак А. Малая теорема Ферма.
  13. Акритас А. Основы компьютерной алгебры с приложениями, стр. 83.
  14. Данциг, Т. Числа — язык науки, 2008, с. 232-234
  15. КВАНТ, 2000, № 3, Сендеров В, Спивак А Малая теорема Ферма
  16. Винберг, 2008, с. 49
  17. Данциг, Т. Числа — язык науки, 2008, p. 234-238
  18. Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, pp. 103—105, ISBN 0-387-94457-5.
  19. Weisstein E. W. Fermat Pseudoprime.. — 2005..
  20. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие. — М.: МФТИ, 2011. — С. 236-237. — 262 с. с. — ISBN 978-5-7417-0377-9.
  21. Williams H. C. Primality testing on a computer (англ.) // Ars Combin. — 1978. — Vol. Т. 5, no. №. 12. — P. 127-185.
  22. Шитов Ю. А. Теоретико-численные методы в криптографии.

Литература[править | править вики-текст]