Математика / Арифметика и теория чисел

Теорема Эйлера: сокращение степени по составному модулю

Теорема Эйлера даёт единичный остаток для основания, взаимно простого с модулем, в степени φ(m). Она работает и с составным модулем, но не позволяет без проверки сокращать показатель любого основания.

Опубликовано: 21 октября 2026 г.Обновлено: 21 октября 2026 г.

Теория чисел Алгебра Страницы с задачами и решениями Есть историческая справка

Формула

a^{\varphi(m)}\equiv1\pmod m,\qquad \gcd(a,m)=1,\quad m>1

Схема Обратимые классы по модулю 15

φ(15) = 8; умножение сохраняет набор классов

Обозначения

$a$: целое основание, безразмерное целое
$m$: целый модуль больше единицы, безразмерное целое
$\varphi(m)$: число обратимых классов остатков по m, неотрицательное целое
$\gcd(a,m)$: наибольший общий делитель основания и модуля, положительное целое

Условия применения

Модуль m > 1 и gcd(a,m) = 1. Для вычисления φ по произведению нужно знать различные простые делители модуля. Показатель n ≥ 0 сокращают по модулю φ(m) только после проверки обратимости. Нулевой остаток показателя означает единицу по модулю m, а не нулевой результат.

Ограничения

При общем делителе основания и модуля формула может давать неверное сокращение даже для большого показателя. Вычисление φ(m) через факторизацию способно быть сложнее самого модульного возведения в степень. Число φ(m) является допустимым периодом, но обычно не обязано быть минимальным для выбранного основания.

Подробное объяснение

Вместо всех ненулевых остатков рассматриваются только обратимые: те, что взаимно просты с m. Их число равно φ(m). Умножение на обратимое a переставляет этот набор, потому что у a есть обратный элемент и разные классы не могут слиться в один.

Сравнение произведений до и после перестановки даёт множитель a в степени, равной числу элементов набора. Произведение обратимых классов тоже обратимо, поэтому его можно сократить. Получается a^φ(m) ≡ 1. Это тот же механизм, что у малой теоремы Ферма, но набор остатков для составного модуля уже не равен всему диапазону 1…m−1.

Для простого p функция φ(p) равна p−1, и теорема возвращается к случаю Ферма. Для составного m значение φ(m) находят по его простым делителям. Например, φ(15) = 8: из пятнадцати классов восемь имеют обратный элемент.

Пусть n = qφ(m)+r. Тогда aⁿ ≡ aʳ, поскольку каждый полный блок φ(m) даёт единицу. Когда r = 0, ответ единица. Если gcd(a,m) не равен единице, этот переход недопустим: например, 2⁴ mod 8 равно нулю, хотя φ(8) = 4 и сокращение показателя дало бы 2⁰ = 1.

Минимальный период степеней может быть меньше φ(m). В примере основания 7 по модулю 15 возврат к единице происходит уже в четвёртой степени. Теорема обещает возврат в степени восемь, но не требует, чтобы раньше его не было. Для минимального периода используется отдельное понятие мультипликативного порядка.

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

Вычислите gcd основания и модуля; если общий делитель больше единицы, не применяйте сокращение показателя по φ.
Найдите φ(m) по доказанному разложению модуля на простые множители либо по другому надёжному способу.
Замените неотрицательный показатель его остатком по φ(m) и вычислите оставшуюся степень целочисленно по модулю.
Проверьте ответ прямым циклом малых степеней или независимым модульным вычислением и не путайте период с минимальным.

Историческая справка

Теорема названа по имени Леонарда Эйлера и относится к теории чисел XVIII века. Её связь с малой теоремой Ферма состоит в переходе от простого модуля к множеству обратимых классов произвольного модуля. В современном учебнике Порица оба утверждения рассматриваются через умножение остатков, что делает общую идею доказательства видимой. Функция φ выступает не просто арифметической формулой по простым делителям, а числом элементов замкнутого набора обратимых классов. Современная групповая интерпретация объясняет и то, почему минимальный период делит φ, но сама по себе не датирует каждую историческую форму доказательства. Здесь имя Эйлера относится к теореме о степенях; алгоритмы факторизации и двоичного возведения рассматриваются отдельно.

Историческая линия формулы

Используется традиционное название «теорема Эйлера» для сравнения a^φ(m) ≡ 1 при взаимной простоте. Функция φ и теорема связаны, но отвечают на разные вопросы: первая считает обратимые классы, вторая задаёт допустимый период степеней. Современное групповое объяснение не приписывается одному историческому доказательству.

Пример

Найдём 7¹⁰⁰ mod 15. Основание 7 взаимно просто с 15. Разложение 15 = 3·5 даёт φ(15) = 15·(1−1/3)·(1−1/5) = 8. Остаток показателя 100 по 8 равен 4, значит достаточно 7⁴. Имеем 7² = 49 ≡ 4, а 7⁴ ≡ 4² = 16 ≡ 1. Ответ 1. Независимая проверка первых степеней даёт остатки 7,4,13,1: цикл длины четыре повторяется 25 раз. Он короче восьми, но согласуется с теоремой, поскольку четыре делит восемь. Все операции относятся к целым числам без физических единиц. Наличие общего делителя потребовало бы другого рассуждения и не могло бы быть исправлено одним уменьшением показателя.

Частая ошибка

Не сокращайте показатель до проверки gcd. Не подменяйте φ(m) числом m−1 для составного модуля. Не считайте нулевой остаток показателя нулевым ответом степени. Не объявляйте φ минимальным периодом каждого основания. Не скрывайте стоимость факторизации, сравнивая алгоритмы только по маленькому конечному показателю.

Практика

Задачи с решением

Нулевой остаток показателя

Условие. Вычислите 3¹⁰⁰ mod 10.

Решение. gcd(3,10) = 1, φ(10) = 4. Показатель 100 делится на 4, поэтому результат 3⁰ mod 10 равен 1.

Ответ. 1.

Нарушенная взаимная простота

Условие. Почему нельзя сократить показатель в 2⁴ mod 8 по φ(8) = 4?

Решение. gcd(2,8) = 2. Прямой расчёт даёт 16 mod 8 = 0, тогда как недопустимое сокращение дало бы 2⁰ = 1.

Ответ. Основание необратимо; правильный остаток 0.

Дополнительные источники

https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_%28Poritz%29/03%3A_Primes_Numbers/3.04%3A_Another_Approach_to_Fermat%27s_Little_and_Euler%27s_Theorems
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/An_Introduction_to_the_Theory_of_Numbers_%28Moser%29/01%3A_Chapters/1.05%3A_Congruences

Связанные формулы

Математика

Быстрое возведение в степень по модулю двоичным методом

$a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$

Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.

Математика

Малая теорема Ферма: степени по простому модулю

$a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$

Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.

Математика

Линейное сравнение: решения через НОД коэффициента и модуля

$ax\equiv b\pmod m\text{ разрешимо}\iff d\mid b,\quad d=\gcd(a,m);\quad x=x_0+k\frac md,\ k=0,\ldots,d-1$

Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.

Математика

Мультипликативный порядок: минимальный период степеней

$\operatorname{ord}_m(a)=\min\{k\ge1:a^k\equiv1\pmod m\},\qquad\operatorname{ord}_m(a)\mid\varphi(m)$

Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.