§ 11.5. Примитивные корни

Пусть простое число. Как уже неоднократно отмечалось, порядок циклической группы равен четному составному числу. Образующая этой группы называется примитивным корнем. Употребление слова «корень» в этом контексте подразумевает какой-то многочлен. Это легко объяснимо. По теореме Ферма все элементы группы корни полиномиального уравнения с коэффициентами из Образующая группы называется примитивным корнем из-за того, что все остальные корни этого уравнения представляются в виде ее степеней. Аналогичный феномен наблюдается при решении уравнений с комплексными коэффициентами. Например, у уравнения есть примитивный корень

Мы приведем конструктивное доказательство существования примитивных корней. Точнее, мы опишем алгоритм для вычисления примитивных корней по модулю Существование примитивных корней по простому модулю было предсказано еще Эйлером, но первое верное доказательство этого факта опубликовал Гаусс в своей книге «Арифметические исследовав ния»(см. [17]).

Теорема о примитивных корнях. Если простое число, то циклическая группа.

Доказательство. Утверждение теоремы очевидным образом выполнено при поэтому можно предполагать, что Выберем произвольный элемент где Ввиду произвольности выбора, на практике всегда можно начинать с Обозначим через порядок элемента Если то мы уже нашли образующую группы

Итак, можно считать, что Класс удовлетворяет уравнению - Поскольку число простое,

из теоремы § 6.4 следует, что это полиномиальное уравнение не может иметь более, чем различных решений. С другой стороны, все элементы множества

являются решениями уравнения Множество состоит ровно из к 1 различных элементов. Поэтому оно содержит все корни этого уравнения. Но, по предположению, значит, в группе найдется какой-то элемент не попавший в множество В частности, не является корнем уравнения и по ключевой лемме порядок элемента не делит

Бели то образующая группы и теорема доказана. Пусть По лемме § 11.4, в группе существует элемент порядок которого равен наименьшему общему кратному чисел

Мы уже заметили, что не делит поэтому Теперь нам остается продолжать описанную процедуру до тех пор, пока мы не найдем элемента порядка Процесс обязательно закончится выбором образующей группы потому что на каждом этапе мы находим все бблыпие натуральные числа но все они меньше, чем

Описанная процедура предоставляет систематический метод поиска образующей группы но при этом не всегда получается наименьшая из возможных образующих. Заметим, что утверждение, обратное теореме, неверно. Например, группа циклическая, хотя число 4 составное. Таким образом, цикличность группы не гарантирует простоты На самом деле можно показать, что циклическая группа тогда и только тогда, когда равно или где простое нечетное число. Доказательство этого результата изложено в [18] ([Д.3]).