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

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

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

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

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

Формула

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

Схема Цикл степеней 2 по модулю 9

Первый возврат к 1: показатель 6

Обозначения

$a$: целое основание, взаимно простое с модулем, безразмерное целое
$m$: целый модуль больше единицы, безразмерное целое
$k$: положительный кандидат на период, положительное целое
$\operatorname{ord}_m(a)$: минимальный положительный период степеней, положительное целое
$\varphi(m)$: число обратимых классов по модулю, положительное целое

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

Нужно m > 1 и gcd(a,m) = 1. Тогда по теореме Эйлера положительный возврат к единице существует. Для поиска по делителям используют известное φ(m) и его факторизацию; кандидатов проверяют модульным возведением в степень. Минимальность проверяется отдельно, а не следует из одного найденного возврата.

Ограничения

У необратимого основания порядок в данном определении отсутствует, даже если последовательность степеней позднее начинает повторяться. Цикл с ненулевым начальным участком — другое понятие. Равенство aᵏ ≡ 1 даёт лишь кратный периоду показатель. Знание порядка не заменяет проверки всех условий при работе с отрицательными степенями.

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

Степени обратимого класса образуют цикл, начинающийся с единицы a⁰. Если первая положительная степень, равная единице, имеет номер d, то умножение на a после этого воспроизводит ту же последовательность. Поэтому aⁿ зависит от остатка n по d.

Любой показатель k с aᵏ ≡ 1 делится на d. Действительно, разделим k на d с остатком r. Тогда aᵏ ≡ aʳ. Если 0 < r < d и это тоже единица, нарушится минимальность d; значит r = 0. Подставляя показатель φ(m) из теоремы Эйлера, получаем делимость d | φ(m).

Самый прямой поиск — последовательно умножать остаток на a до первого возвращения к единице. Для большого модуля выгоднее начинать с φ(m) и сокращать кандидат по его простым делителям: если a^(d/q) ≡ 1, кандидат d можно заменить на d/q. Проверки повторяют, пока дальнейшее сокращение невозможно.

Для 2 по модулю 9 степени дают 2,4,8,7,5,1, поэтому порядок равен 6. Для 2 по модулю 7 цикл 2,4,1 имеет длину 3, хотя φ(7) = 6. Общее число обратимых классов не обязано совпадать с размером цикла каждого основания.

Основание с порядком φ(m) называют первообразным корнем по этому модулю. Не у каждого модуля такие основания существуют. Например, по модулю 8 у каждого обратимого остатка квадрат равен единице, поэтому порядок не превышает 2, тогда как φ(8) = 4. Это показывает границы идеи одного цикла для всех обратимых классов.

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

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

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

Понятие порядка входит в современное описание арифметики сравнений через обратимые классы и циклы их степеней. Оно уточняет теоремы Ферма и Эйлера: вместо общего показателя возвращения задаёт минимальный для конкретного основания. Учебник Порица выделяет Multiplicative Order and Applications в отдельный раздел, связывая определение с практикой вычисления остатков. Исторический контекст относится к развитию теории чисел и группового языка XIX века, но отдельную дату введения именно этой нотации по используемым источникам не устанавливают. Содержательно важен переход от наблюдаемого повторения нескольких чисел к доказанному минимальному периоду. Этот переход требует обратимости, конечности множества и проверки минимальности, а не только длинной таблицы вычислений.

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

Мультипликативный порядок — стандартное понятие теории групп, применённое к обратимым остаткам. Оно не имеет здесь отдельной персональной атрибуции. Имена Ферма и Эйлера относятся к связанным теоремам, гарантирующим возврат в определённой степени, а не обязательно минимальный период.

Пример

Найдём порядок 2 по модулю 9. Числа взаимно просты, φ(9) = 6. Последовательные остатки: 2¹ ≡ 2, 2² ≡ 4, 2³ ≡ 8, 2⁴ ≡ 7, 2⁵ ≡ 5, 2⁶ ≡ 1. Раньше единицы нет, значит порядок равен 6. Независимая проверка по делителям φ: кандидаты 1,2,3 дают 2,4,8 и не подходят; 6 даёт единицу. Теперь для 2¹⁰⁰ остаток показателя по 6 равен 4, поэтому результат 7. Эта проверка минимальности отличается от одной подстановки 2⁶ ≡ 1: без просмотра меньших делителей мы знали бы лишь допустимый период. Все значения безразмерны и вычисляются в целых остатках, а не приближёнными десятичными степенями.

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

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

Практика

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

Период короче φ

Условие. Найдите порядок 2 по модулю 7.

Решение. Степени дают остатки 2,4,1. Первый возврат происходит при показателе 3; он делит φ(7) = 6.

Ответ. ord₇(2) = 3.

Обратимый остаток mod 8

Условие. Найдите порядок 3 по модулю 8 и проверьте, является ли 3 первообразным корнем.

Решение. 3¹ ≡ 3, 3² = 9 ≡ 1. Порядок равен 2, а φ(8) = 4, поэтому максимальный размер набора не достигнут.

Ответ. Порядок 2; первообразным корнем не является.

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

https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_%28Poritz%29/03%3A_Primes_Numbers/3.03%3A_Multiplicative_Order_and_Applications
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

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

Математика

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

$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 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.

Математика

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

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

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

Математика

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

$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 — этот НОД.