Русская Википедия:Малая теорема Ферма

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Ма́лая теоре́ма Ферма́ — теорема теории чисел, которая утверждает, чтоШаблон:Sfn:Шаблон:Теорема На языке теории сравнений: <math>a^{p-1}</math> сравнимо с 1 по простому модулю <math>p</math>. Формальная запись: <math>a^{p-1}\equiv 1 \pmod p </math>

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

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

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

История

Файл:Pierre de Fermat.jpg
Пьер Ферма

Пьер Ферма сформулировал исходное утверждение теоремы в письме 1640 года к французскому математику Бернару Френиклю[3]: Шаблон:Начало цитаты Каждое простое число эквивалентно [в оригинале: измеряет] степени минус один с любым основанием и показателем, равным данному простому числу минус один… И это утверждение, как правило, справедливо для всех оснований и всех простых чисел. Я бы Вам прислал доказательство, если бы оно не было таким длинным. Шаблон:Oq Шаблон:Конец цитаты

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

Сам Ферма оставил свою теорему без доказательства. Первым математиком, нашедшим доказательство, был Готфрид Вильгельм Лейбниц, из рукописей которого следует, что доказательство ему было известно до 1683 года. Лейбниц не знал о результате Ферма и открыл теорему независимоШаблон:Sfn. Однако работа Лейбница не была опубликована, и доказательство в 1736 году обнародовал Эйлер в статье Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio[4]. В 1806 году шотландский математик Джеймс Айвори опубликовал доказательство, основанное на том, что если <math>x</math> пробегает полную систему вычетов по модулю <math>p</math>, то для любого <math>a,</math> не кратного <math>p,</math> произведение <math>ax</math> также пробегает полную систему вычетов по модулю <math>p;</math> эта идея лежит в основе современных доказательств[5].

Число <math>\frac{a^{p-1} - 1}{p}</math> называется частным Ферма. Русский математик Д. А. Граве предположил, что частное Ферма никогда не делится на <math>p.</math> Для простых чисел, не превышающих 1000, это действительно так, однако вскоре был обнаружен контрпример: для <math>p=1093, a=2</math> частное Ферма делится на 1093[6].

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

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

Шаблон:Теорема

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

Легко показать что эта формулировка сводится к изначальной. Так, если <math>a</math> делится на <math>p</math>, то <math>a\equiv 0 \pmod p</math> и <math>a^p\equiv 0 \pmod p</math>, т.е. <math>a^p\equiv a \pmod p</math>. Если же <math>a</math> не делится на <math>p</math>, то выражение <math>a^{p}\equiv a \pmod p </math> эквивалентно выражению <math>a^{p-1}\equiv 1 \pmod p </math>Шаблон:Sfn.

Как основная, так и альтернативная формулировки могут быть использованы для проверки, является ли заданное число простым (см. ниже), однако основная формулировка надёжнее в том смысле, что отбраковывает больше составных чисел. Пример: проверим, является ли <math>6</math> простым числом. Пусть <math>a = 4.</math> В альтернативной формулировке получается <math>4^6 = 4096 = 682\times 6+4</math>, а это сравнимо с 4 mod 6. То есть число 6 не отбраковано, его простота не опровергнута. Если же вернуться к оригинальной теореме: <math>a^{p-1}\equiv 1 \pmod p</math>, то <math>4^{6-1} = 4^5 = 1024 = 170\times 6+4</math>, а это не сравнимо с 1 mod 6, как должно быть в случае, если p — простое число. Таким образом, основная формулировка более эффективна при отбраковке составных чисел.

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

Шаблон:Hider

Шаблон:Hider

Шаблон:Hider

Шаблон:Hider

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

  • Если <math>p</math> — простое число, то в поле <math>\mathbb Z_p</math> выполняется равенство <math>a^{-1} = a^{p-2}</math>[7].
  • Если <math>p</math> — простое число, отличное от 2 и 5, то число <math>10^{p-1} - 1</math>, в десятичной записи которого присутствуют только цифры <math>9</math>, делится на <math>p</math>. Отсюда следует, что для любого целого числа <math>N</math>, которое не делится ни на 2, ни на 5, можно подобрать число, состоящее только из девяток, которое делится на <math>N</math>. Этот факт используется в теории признаков делимости и периодических дробейШаблон:Sfn.
  • Малая теорема Ферма позволяет находить простые делители чисел вида <math>a^4+a^3+a^2+a+1</math> и <math>a^{2^n}+1</math>[8].
  • Обобщением малой теоремы Ферма на алгебраические числа является теорема, сформулированная Шаблон:Нп5 в 1839 году: пусть <math>a_1,\dots,a_d</math> — корни нормированного многочлена <math>f\in \mathbb Z[x]</math> степени Шаблон:Math, а Шаблон:Math — простое число. Тогда <math>a_1^p + a_2^p + \dots + a_d^p \equiv a_1 + \dots + a_d\pmod p </math>Шаблон:Sfn.
  • Из малой теоремы Ферма следует теорема Вильсона: Натуральное число <math>p>1</math> является простым тогда и только тогда, когда <math>(p-1)!+1</math> делится на p.

Шаблон:Hider

Приложения

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

Шаблон:Main Шаблон:Main

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

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

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

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

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

Алгоритм RSA

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

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Добротная статья

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Энциклопедия элементарной математики, Книга 1, Арифметика, Александров П. С., Маркушевич А. И., Хинчин А. Я., 1961.— С. 280
  2. ↑ Шаблон:Книга
  3. ↑ Шаблон:Книга
  4. ↑ David C. Marshall, Edward Odell, Michael Starbird. Number Theory Through Inquiry Шаблон:Wayback. — 2006. — pp. 62—63.
  5. ↑ Шаблон:MacTutor Biography
  6. ↑ Шаблон:Книга
  7. ↑ Акритас А. Основы компьютерной алгебры с приложениями, стр. 83.
  8. ↑ КВАНТ, 2000, № 3, Сендеров В, Спивак А Малая теорема Ферма
  9. ↑ Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, pp. 103—105, ISBN 0-387-94457-5.
  10. ↑ Шаблон:Статья
  11. ↑ Шаблон:Книга
  12. ↑ Шаблон:Статья
  13. ↑ Шитов Ю. А. Теоретико-численные методы в криптографии.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Малая_теорема_Ферма&oldid=10322412