Первообразный корень (теория чисел)
порождающая мультипликативной группы вычетов по модулю n / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Первообразный корень (теория чисел)?
Кратко изложите эту статью для 10-летнего ребёнка
ПОКАЗАТЬ ВСЕ ВОПРОСЫ
У этого термина существуют и другие значения, см. Первообразный корень.
Первообразный корень по модулю m ― целое число g такое, что
и
- при
где ― функция Эйлера. Другими словами, первообразный корень — это образующий элемент мультипликативной группы кольца вычетов по модулю m.
Чтобы не проверять все от до , достаточно проверить три условия:
- Является ли числом взаимно простым с , и если нет - то это не первообразный корень.
- Так как - всегда чётное число для всех , то имеет как минимум один простой делитель - простое число , следовательно, для того, чтобы отсеять значительное количество не-корней, достаточно проверить для числа, подходящего на первообразный корень по модулю .[1] Если результат +1 m , то g - не корень, в ином случае результат -1 m, когда g - это возможно первообразный корень.
- Далее следует убедиться, что для всех , где - простой делитель числа , полученный в результате его факторизации.