§ 11.6. Вычисление порядков

Здесь мы применяем метод Гаусса, описанный в § 11.5, к поиску образующей группы Но сначала нам нужно придумать простой способ вычисления порядков элементов группы

Пусть простое нечетное число и Вычислим порядок к элемента . По теореме Лагранжа порядок к должен делить число порядок группы Допустим, нам известно разложение числа на простые множители:

где простые, натуральные числа. Заметим, что если мы не сможем разложить на множители число то мы вообще не сможем воспользоваться методом Гаусса. Итак, поскольку к делит найдутся такие неотрицательные целые числа что

причем

Значит, для вычисления порядка к нам достаточно определить показатели Покажем, как находится остальные показатели находятся аналогично. Сначала выписываем последовательность

по модулю Заметим, что по теореме Ферма первый элемент этой последовательности всегда равен 1. Предположим, что наибольшее неотрицательное число, для которого

Тогда либо либо

Из сравнения (6.1) и ключевой леммы вытекает, что к делит С другой стороны, благодаря (6.2), мы видим, что к не делит Другими словами, делит произведение

но не делит

Такое возможно лишь в случае что дает нам алгоритм вычисления показателя

Вернемся к нашему примеру. Как упоминалось в доказательстве теоремы о примитивных корнях, в качестве отправной точки метода Гаусса удобно выбрать 2. Определим порядок этого элемента. Прежде всего, согласно разработанной схеме, нам нужно разложить порядок группы на простые множители. Имеем:

Далее вычисляем

Итак, простое число 2 входит в разложение порядка элемента 2 с кратностью Повторим те же действия со следующим простым делителем 5. Несложные вычисления показывают, что

Значит, кратность пятерки в порядке элемента 2 равна и 2 имеет порядок В частности, 2 не является образующей группы

Далее нам нужно выбрать другой элемент группы отличный от степеней элемента 2, скажем, 3. Вычислим его

порядок. Имеем:

Из первого соотношения мы заключаем, что 8 делит порядок элемента 3, а из второго — что 5 этот порядок не делит. Следовательно, порядок элемента 3 равен 8.

Далее, как мы делали в § 11.4, нам предстоит разложить на множители (порядок элемента 2) и (порядок элемента 3). Поскольку мы выбираем Это, в обозначениях § 11.4, дает Теперь, следуя рецепту из доказательства леммы § 11.4, строим элемент

группы порядок которого равен Таким образом, 7 — образующая группы

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)