Математика · объяснение и практика
Когда малая теорема Ферма сокращает большую степень
Уменьшаем большой показатель по малой теореме Ферма, проверяем простоту модуля и взаимную простоту основания и не принимаем успешную проверку за доказательство простоты.

В теме Теория чисел: углубление · Учебная карта
Главная мысль
Если p простое и a не делится на p, то aᵖ⁻¹ ≡ 1 по модулю p. Поэтому неотрицательный показатель можно уменьшать по модулю p−1. Условие на основание существенно: при a, кратном p, такая замена способна дать неверный единичный остаток.
Как теорема сокращает объём вычислений
Чтобы найти остаток 3¹⁰⁰ по модулю семь, не нужно выписывать огромное число. Простота семи и отсутствие делимости тройки на семь позволяют использовать 3⁶ ≡ 1. Представим показатель как 100 = 6·16+4. Тогда шестнадцать полных блоков дают единичный остаток, а остаётся 3⁴ = 81, что оставляет остаток четыре.
Этот переход использует умножение сравнений и разложение степени на произведение блоков. Показатель не делится на шесть в обычном равенстве чисел; меняется лишь способ вычисления остатка. Поэтому нельзя объявить 3¹⁰⁰ равным 3⁴ как целые числа. Они сравнимы по выбранному модулю, который должен сохраняться в записи.
Почему нужны оба условия
Для простого p умножение ненулевых остатков 1, 2, …, p−1 на обратимое a переставляет их. Произведение новых остатков равно произведению старых по модулю p, поэтому aᵖ⁻¹(p−1)! ≡ (p−1)!. Все множители факториала обратимы, и его можно сократить. Получается единичный остаток требуемой степени.
Если a делится на p, обратимости нет. Например, 5⁴ по модулю пять равно нулю. Формальное уменьшение показателя четыре по модулю четыре до нуля дало бы 5⁰ = 1 и ошибочный ответ. Другая форма теоремы, aᵖ ≡ a, действует для всех целых a, но она не разрешает ту же безусловную замену показателя.
Пример
Найдите остаток 2²⁰ по модулю семь.
Двадцать даёт остаток два при делении на шесть. Поэтому 2²⁰ ≡ 2² ≡ 4 по модулю семь. Основание два не кратно семи, так что сокращение показателя допустимо.
Чего успешное сравнение не доказывает
Обратное утверждение неверно: составное число может пройти проверку по отдельному основанию. Например, 341 = 11·31, а 2¹⁰ = 1024 оставляет остаток один по модулю 341. Значит, 2³⁴⁰ тоже оставляет один, хотя модуль составной. Один успешный тест не является сертификатом простоты.
В вычислительной задаче сначала устанавливают применимость теоремы, затем сокращают показатель и считают короткую степень с остатками. При составном модуле существуют другие методы, включая теорему Эйлера для взаимно простого основания. Однако заменять p−1 на произвольное удобное число нельзя. Каждое сокращение показателя должно опираться на доказанный период или соответствующую теорему с проверенными условиями.
От чтения к действию
А теперь — вы
Частые вопросы
Можно использовать p−1 для любого положительного модуля?
Нет. Малая теорема Ферма требует простого p. Для составных модулей нужен другой обоснованный период или другая теорема.
Единичный остаток доказывает простоту модуля?
Не сам по себе. Существуют составные числа, проходящие подобную проверку по выбранному основанию.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как уменьшать показатель степени по теореме Эйлера
Сокращаем показатель степени при составном модуле через функцию Эйлера, проверяем взаимную простоту и отличаем гарантированный период от наименьшего.
Открыть темуОбратный элемент по модулю: условие существования и проверка
Находим обратный множитель по модулю, проверяем условие взаимной простоты и отличаем обратный остаток от обычной дроби.
Открыть тему