Главная > Математика > Введение в теорию чисел. Алгоритм RSA
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 9.6. Циклические подгруппы

Как обычно, обозначим символом операцию на конечной группе Определим степень элемента а этой группы стандартным образом:

и рассмотрим множество его степеней:

Очевидно, это конечное множество. Мы сказали «очевидно», потому что конечное множество, так что не может иметь бесконечного числа элементов. Но такое может быть только в том случае, если существуют равные степени а с разными показателями. Другими словами, найдутся такие натуральные что

Пусть а — обратный элемент к а. Умножая обе части равенства на получим: единичный элемент. Следовательно, для данного элемента найдется натуральное число к, для которого Таким образом,

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

Чему равен порядок группы Предположим, что к — наименьшее натуральное число, обладающее свойством Если то мы можем разделить на к с остатком: где . Значит,

Но так что Иначе говоря, любая степень а, показатель которой больше к, равна степени с некоторым меньшим показателем. Следовательно,

Более того, все эти элементы различны. Действительно, если то . С другой стороны, по предположению, меньше к — наименьшего натурального числа, обладающего таким свойством. Значит, т.е. Таким образом, порядок группы равен к.

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

• множество степеней а является подгруппой в G;

• порядок группы равен наименьшему натуральному к, для которого

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

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

В качестве простого приложения разработанного метода определим структуру группы порядок которой — простое число Примером такой группы служит с операцией сложения. Предположим, что Н — какая-то подгруппа в По теореме Лагранжа порядок Н должен делить порядок равный Так как простое, то порядком Я может быть только либо 1, либо . В первом случае а во втором Таким образом, в группе есть только две подгруппы. Теперь выберем произвольный элемент аевби обозначим через Н циклическую подгруппу, им порожденную. Так как то Н не может состоять только из единичного элемента и значит, . В частности, циклическая группа, причем любой ее элемент, отличный от является образующей. Суммируем эти результаты в следующей теореме.

Теорема о группах простого порядка. Если порядок группы G прост, то

• G циклическая;

• G имеет только две подгруппы: саму ;

• любой элемент группы за исключением является образующей всей группы.

Итак, любая группа простого порядка — циклическая. Обратное же, вообще говоря, неверно. Например, порядок группы равен но она циклическая, и 2 — ее образующая. Мы вернемся к этому примеру в главе 11, где докажем теорему о примитивных корнях.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление