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

§ 9.7. В поисках подгрупп

Применим результаты предыдущего параграфа к определению всех подгрупп группы Мы уже отмечали в § 9.5, что для этого достаточно найти в ней подгруппы порядков 2 и 3. Но 2 и 3 — простые числа, так что, согласно теореме из § 9.6, соответствующие подгруппы должны быть циклическими. Более того, они полностью определяются своими образующими. Поэтому нам достаточно понять, какие из элементов имеют порядок 2, а какие — 3.

Так как то порядок равен 3. Кроме того,

Значит, также имеет порядок 3. Поскольку каждая из осевых симметрий сама себе обратна, ее порядок равен 2. Циклическая подгруппа, порожденная имеет вид:

откуда следует, что она совпадает с подгруппой, порожденной Следовательно, единственная подгруппа в имеющая порядок 3. Каждая из осевых симметрий задает свою подгруппу в порядка 2, а именно,

Итак, мы доказали, что кроме в группе существуют только циклические подгруппы. Следует ли отсюда, что имеет только циклические подгруппы? На самом деле нет, поскольку будучи подгруппой в себе самой, не является циклической. Действительно, если бы она была циклической, то ее образующая имела бы порядок 6. Но, как мы видели, любой из ее элементов имеет порядок 1, 2 или 3. Однако все собственные подгруппы в циклические. Подгруппа называется собственной, если она содержит хотя бы

один элемент, отличный от единичного, и не совпадает при этом со всей группой

Далее мы хотим привести пример группы, которая не только сама не является циклической, но и содержит собственную нециклическую подгруппу. Рассмотрим

с операцией умножения по модулю 16. Эта группа имеет порядок По теореме Лагранжа у нее могут быть подгруппы только порядков 1, 2, 4 или 8. Подгруппы порядков 1 и 8 определяются мгновенно, это соответственно.

Для выделения остальных подгрупп мы должны вычислить порядки каждого элемента из Это можно сделать довольно быстро: 7, 9 и 15 имеют порядок 2, а 3, 5, 11 и 13 — порядок 4. Значит в группе нет элемента порядка 8. В частности, она не является циклической.

Можно ли утверждать, что любая собственная подгруппа в циклическая? Напомним, что подгруппа простого порядка должна быть циклической. Поэтому порядок нециклической подгруппы обязан быть составным числом, меньшим восьми, и одновременно делить 8. Значит, если такая подгруппа существует, то ее порядок равен 4. Кроме того, порядок любого ее элемента должен быть меньше 4, поскольку в противном случае она будет циклической. Ввиду теоремы Лагранжа отсюда вытекает, что все элементы искомой подгруппы, корме 1 должны иметь порядок 2. Но имеет в точности 3 таких элемента, которые вместе с единичным образуют множество из четырех элементов, а именно,

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

Мы воспользуемся результатами предыдущего параграфа для обобщения теоремы Ферма на случай составных модулей.

Теорема Эйлера. Пусть натуральные числа. Если то

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

что равносильно сравнению из теоремы Эйлера.

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