Что такое малая теорема Ферма?
Малая теорема Ферма — один из краеугольных камней теории чисел. Она утверждает, что если p — простое число, а a — целое число, не делящееся на p (то есть НОД(a, p) = 1), то a в степени (p − 1) при делении на p даёт остаток 1. В символьной записи: \(a^{p-1} \equiv 1 \pmod{p}\). Существует и более общая форма, верная для любого целого a: \(a^{p} \equiv a \pmod{p}\).
Как пользоваться калькулятором
Введите основание a и значение p. Калькулятор проверит, является ли p простым, вычислит НОД(a, p), а затем найдёт оба значения — \(a^{p-1} \bmod p\) и \(a^{p} \bmod p\) — с помощью быстрого возведения в степень по модулю. Если p простое и НОД(a, p) = 1, первый результат всегда будет равен 1, что подтверждает теорему. Если же эти условия не выполняются, значение \(a^{p-1}\) показывается как n/a, потому что теорема в этом случае не гарантирует результат 1.
Разбор формулы
При возведении в степень по модулю основание последовательно возводится в квадрат с одновременным приведением по модулю p, благодаря чему даже большие показатели остаются легко вычислимыми. Эта теорема лежит в основе тестов на простоту (тест Ферма), математики ключей в шифровании RSA и вычисления обратных элементов по модулю: ведь \(a^{p-2} \bmod p\) даёт обратный к a по модулю простого числа p.
Разбор примера
Пусть a = 2 и p = 7. Так как 7 — простое число и НОД(2, 7) = 1, мы ожидаем, что $$2^{6} \bmod 7 = 64 \bmod 7 = 1.$$ ✔ Общая форма даёт $$2^{7} \bmod 7 = 128 \bmod 7 = 2,$$ что совпадает с \(a \bmod 7 = 2\). ✔
Частые вопросы
А если p не простое? Тогда теорема может не выполняться. Калькулятор отметит, что p не является простым, и осмысленным останется только общее значение \(a^{p} \bmod p\), причём оно не обязательно будет равно a.
А если a кратно p? Тогда НОД(a, p) ≠ 1, и значение \(a^{p-1} \bmod p\) не будет равно 1 (оно равно 0). При этом общая форма \(a^{p} \equiv a\) по-прежнему верна.
Можно ли с его помощью находить обратные элементы по модулю? Да — для простого p значение \(a^{p-2} \bmod p\) является мультипликативным обратным к a по модулю p.
