первообразный корень по модулю n

Первообразный корень по модулю m ― целое число g такое, что и при где ― функция Эйлера. Другими словами, первообразный корень — это образующий элемент мультипликативной группы кольца вычетов по модулю m. Чтобы не проверять все от до , достаточно проверить три условия: 1. * Является ли числом взаимно-простым с , и если нет - то это не первообразный корень. 2. * Так как , всегда число четное, для всех чисел , то имеет как минимум один простой делитель - простое число , то следовательно, для того, чтобы отсеять значительное количество не-корней, достаточно проверить для числа, подходящего на первообразный корень по модулю . Если результат +1 m , то g - не корень, в ином случае результат -1 m, когда g - это возможно-первообразный корень. 3. * Далее следует убедиться, что для всех , где - простой делитель числа , полученный в результате его факторизации.