Математика · объяснение и практика

Как уменьшать показатель степени по теореме Эйлера

Сокращаем показатель степени при составном модуле через функцию Эйлера, проверяем взаимную простоту и отличаем гарантированный период от наименьшего.

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

Главная мысль

Если НОД(a,n) = 1 и n ≥ 2, теорема Эйлера даёт aᵠ⁽ⁿ⁾ ≡ 1 по модулю n. Поэтому показатель неотрицательной степени можно уменьшать по модулю φ(n). Значение φ(n) является допустимым блоком повторения, но не обязано быть самым коротким.

Какие остатки участвуют в обобщении Ферма

При простом модуле все ненулевые остатки обратимы. При составном среди них появляются числа с общими делителями, поэтому нельзя просто использовать количество n−1. Теорема Эйлера выбирает только остатки, взаимно простые с n. Их число равно φ(n), и умножение на обратимое a переставляет именно этот набор, не смешивая его с необратимыми остатками.

Произведение всех выбранных остатков после такой перестановки сохраняется. Каждый из φ(n) множителей получил дополнительный множитель a, поэтому возникает aᵠ⁽ⁿ⁾. Исходное произведение можно сократить, поскольку оно тоже взаимно просто с модулем. Этот аргумент объясняет одновременно появление функции Эйлера и необходимость условия НОД(a,n) = 1, а не только предлагает готовую степень.

Как получить короткий расчёт остатка

Найдём остаток 7²²² по модулю пятнадцать. Различные простые делители пятнадцати — три и пять, поэтому φ(15) = 15·(2/3)·(4/5) = 8. Семёрка взаимно проста с пятнадцатью. Представим 222 = 8·27+6: полные блоки можно заменить единицами, остаётся вычислить 7⁶ по тому же модулю.

Квадрат семи даёт остаток четыре, четвёртая степень остаток один, шестая снова четыре. Поэтому ответ равен четырём. Заметим, что для этой семёрки повторение уже произошло на четвёртой степени, меньше φ(15). Теорема обеспечила верный блок восемь, но не обещала его минимальность. При вычислении можно использовать и более короткий период, если он отдельно доказан.

Пример

Каков остаток 3³⁵ по модулю десять?

Функция Эйлера даёт φ(10) = 4, а тройка взаимно проста с десятью. Показатель 35 оставляет три при делении на четыре, поэтому достаточно 3³ = 27. Остаток равен семи.

Когда сокращение недопустимо

Для a = 6 и n = 12 взаимная простота нарушена. Хотя φ(12) = 4, степень 6⁴ оставляет остаток ноль, а не единицу. Замена показателя четыре на ноль дала бы 6⁰ = 1 и неверный ответ. Наличие известной функции φ для модуля не отменяет проверки самого основания.

Теорема о степенях не говорит, что у каждого модуля есть один одинаковый минимальный период для всех целых оснований. Обратимые основания образуют особый набор, а необратимые требуют отдельного анализа. В решении полезно записать три короткие строки: проверка НОД, вычисление φ(n), разложение показателя на полные блоки. Такой порядок сохраняет условия применения даже при очень большом исходном показателе.

От чтения к действию

А теперь — вы

Каков остаток 7¹⁰³ по модулю десять?

Частые вопросы

Для простого модуля результат отличается от Ферма?

Нет. При простом p функция φ(p) равна p−1, и теорема Эйлера даёт привычную малую теорему Ферма для основания, не кратного p.

Период обязательно равен φ(n)?

Нет. Это гарантированный допустимый показатель единичного остатка для обратимого основания. Наименьший положительный показатель может быть меньше.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться