Калькулятор малой теоремы Ферма

Как пользоваться калькулятором

1. Введите основание \(a\) в поле Основание (a). Оно должно удовлетворять условию \(1 \le a < p\).
2. Введите простое число в поле Простой модуль (p) (например, 2, 3, 5, 7, 11…).
3. Прочитайте результат Результат a^(p−1) mod p — остаток от деления \(a^{p-1}\) на \(p\).
4. Проверьте поле Теорема выполняется? — оно показывает «Да», когда остаток равен 1, что верно для любого корректного ввода.

Если ввести составной модуль, основание вне допустимого диапазона или \(a \ge p\), калькулятор вместо результата покажет сообщение об ошибке.

Что означает малая теорема Ферма

Малая теорема Ферма, сформулированная Пьером де Ферма в 1640 году, — один из краеугольных камней элементарной теории чисел. Она говорит, что простые числа накладывают на степени удивительно регулярную структуру: какое бы основание \(a\) вы ни выбрали (при условии, что \(p\) не делит \(a\)), степень \(a^{p-1}\) всегда даёт в точности 1 по модулю \(p\). Иными словами, \(a^{p-1}\) всегда кратно \(p\) плюс единица.

Почему это важно? Во-первых, это мощный вычислительный приём. Вместо прямого вычисления огромной степени вроде \(3^{100}\) можно привести показатель по модулю \(p-1\) и работать с гораздо меньшими числами — этот приём постоянно используется в модулярной арифметике. Во-вторых, теорема лежит в основе проверки простоты: если \(a^{p-1} \bmod p \ne 1\) для некоторого \(a\), то \(p\) заведомо не простое. На этой идее построен тест Ферма и, в усовершенствованном виде, тест Миллера — Рабина, применяемый для поиска больших простых чисел.

В-третьих, теорема необходима в криптографии. Шифрование и расшифровка RSA — это по существу модульное возведение в степень, и именно малая теорема Ферма (вместе с её обобщением — теоремой Эйлера) гарантирует, что расшифрованное сообщение совпадает с исходным. Она также напрямую приводит к формуле нахождения обратного элемента по модулю простого числа: поскольку \(a^{p-1} \equiv 1 \pmod{p}\), обратный элемент к \(a\) — это просто \(a^{p-2} \bmod p\).

Как интерпретировать результат

Для любого корректного ввода — простого \(p\) и основания \(a\) с \(1 \le a < p\) — калькулятор всегда вернёт 1 и «Да». В этом и состоит содержание теоремы: она утверждает нечто о всех таких парах, а не только о некоторых. Если хотите увидеть, почему для составных чисел теорема не работает, попробуйте \(a = 2\), \(p = 9\): \(2^8 = 256\), а \(256 \bmod 9 = 4 \ne 1\). Теорема — односторонний тест: составное число всегда «проваливает» тест хотя бы для одного основания, тогда как успешное прохождение само по себе ещё не доказывает простоту (см. заметку о числах Кармайкла ниже).

Допущения, ограничения и советы

• Модуль должен быть простым. Для составных модулей теорема в общем случае не выполняется. Для составного \(n\) используйте вместо неё теорему Эйлера \(a^{\varphi(n)} \equiv 1 \pmod{n}\), где \(\varphi\) — функция Эйлера, а \(\gcd(a, n) = 1\).
• Основание не должно быть кратно \(p\). Если \(a \equiv 0 \pmod{p}\), то \(a^{p-1} \equiv 0\), а не 1. Эквивалентная форма \(a^p \equiv a \pmod{p}\) в этом случае всё равно выполняется.
• Тесты Ферма можно обмануть. Существуют составные числа, называемые числами Кармайкла (наименьшее — 561), которые удовлетворяют сравнению \(a^{n-1} \equiv 1 \pmod{n}\) для любого \(a\), взаимно простого с \(n\). Поэтому успешное прохождение одного теста не является доказательством простоты.
• Работайте с приведёнными показателями. При вычислениях вручную сочетайте теорему с последовательным возведением в квадрат: приводите показатели по модулю \(p-1\), а промежуточные произведения — по модулю \(p\), чтобы числа оставались малыми.
• Связанные инструменты. Для систем сравнений см. калькулятор китайской теоремы об остатках; для деления в модулярной арифметике естественным дополнением служит калькулятор обратного по модулю.