Для каких модулей n существуют первообразные корни?

Мультипликативная группа циклическая и имеет первообразные корни только для n = 2, 4, p^k и 2p^k, где p — нечётное простое число, а k ≥ 1.

Сколько всего первообразных корней существует по модулю n?

Если мультипликативная группа циклическая, количество первообразных корней в точности равно φ(φ(n)), где φ — функция Эйлера.

Как проверяется, что число g — первообразный корень?

Проверяется условие НОД(g, n) = 1 и для всех простых делителей q числа φ(n) вычисляется g^(φ(n)/q) mod n. Если ни один результат не равен 1, g — первообразный корень.

Каково максимальное поддерживаемое значение модуля n?

Инструмент поддерживает вычисления для целых чисел n в диапазоне от 2 до 10¹².

Что произойдет, если для выбранного n первообразных корней не существует?

Инструмент определит структуру группы, вычислит λ(n) < φ(n) и сообщит, что группа не является циклической.

Elysia Tools

Навигация

Math & Numbers

Поиск первообразных корней по модулю n

Ищет первообразные корни по модулю n: проверяет, что n ∈ {2, 4, p^k, 2p^k} (циклическая мультипликативная группа), находит наименьший корень с сертификатом g^(φ/q) ≠ 1 для каждого простого q | φ(n), считает их количество как φ(φ(n)), выводит до 50 корней или проверяет, равен ли порядок кандидата g числу φ(n). До 10¹².

Запуск

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

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

Примеры

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

Связано

Поиск первообразных корней по модулю n

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

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

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

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

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

Обзор

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

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

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

Примеры

1. Поиск всех первообразных корней для простого модуля 23

2. Проверка кандидата в генераторы для n = 41

FAQ

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

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

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

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

Проверка квадратичного вычета (символы Лежандра/Якоби)

Интерпретация КЩС (AG / ΔAG)

Калькулятор концентрации ДНК (по поглощению A260)

Калькулятор чистоты OD260/230 (загрязнение солями/органикой)