Что такое мультипликативный порядок ord_n(a)?

Это наименьшее натуральное число k ≥ 1, для которого a в степени k дает остаток 1 при делении на n.

Почему для вычисления порядка требуется gcd(a, n) = 1?

Если a и n имеют общий делитель больше 1, любая степень a делится на этот делитель и никогда не даст остаток 1 по модулю n.

Что означает, если ord_n(a) = φ(n)?

Это означает, что элемент a является первообразным корнем по модулю n и порождает всю мультипликативную группу (Z/nZ)*.

Каковы ограничения на значения a и n?

Модуль n поддерживается в диапазоне от 2 до 10¹², а число a может быть произвольным целым числом до 10⁵¹².

В чем разница между φ(n) и λ(n) при поиске порядка?

φ(n) — функция Эйлера, а λ(n) — функция Кармайкла, задающая максимально возможный порядок элемента в мультипликативной группе по модулю n.

Elysia Tools

Навигация

Math & Numbers

Мультипликативный порядок по модулю n (порядок элемента)

Вычисляет мультипликативный порядок ord_n(a) — наименьшее k ≥ 1 с a^k ≡ 1 (mod n) (требуется gcd(a, n) = 1). Алгоритм стартует с φ(n) и последовательно отбрасывает простые множители, проверяя a^(ord/p); вывод включает таблицу степеней a, доказательство минимальности (a^(k/p) ≢ 1 для каждого простого p | k), порождённую циклическую подгруппу <a>, а также отметки, является ли a первообразным корнем (ord = φ(n)) или достигает максимального порядка (ord = λ(n)). Классика: ord_7(3) = 6 = φ(7), 3 — первообразный корень по модулю 7; ord_15(2) = 4 < φ(15) = 8.

Запуск

Запустить этот инструмент

Заполните форму, запустите инструмент и посмотрите результат на этой же странице.

Примеры

Примеры для этого инструмента

Связано

Мультипликативный порядок по модулю n (порядок элемента)

Запустить этот инструмент

Примеры для этого инструмента

Продолжить с похожими инструментами и темами

Узнайте, когда использовать этот инструмент, что он поддерживает и как его применяют пользователи.

Ключевые факты

Обзор

Когда использовать

Как это работает

Сценарии использования

Примеры

1. Проверка первообразного корня по модулю 7

2. Анализ подгруппы четного составного модуля

FAQ

Примеры Обработки Изображений Web Python

Примеры Обработки Изображений Android Java

Примеры Обработки Изображений Android Kotlin

Примеры Обработки Изображений Web Rust

Калькулятор функции Кармайкла λ(n)

Китайская теорема об остатках (система сравнений)

Генератор перестановок / сочетаний / подмножеств (с повторами)

Калькулятор функции Эйлера φ(n)