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

§ 9.5. Подгруппы

Бели подмножество группы является группой относительно операции в то его называют подгруппой группы Ввиду важности понятия подгруппы для дальнейшего выпишем его более формальное определение.

Пусть группа с операцией. Непустое подмножество называется подгруппой группы если

(1) для любой пары

(2) единичный элемент группы содержится в

(3) если то обратный к нему элемент а также входит в Н.

По терминологии, введенной в § 9.1, условие (1) означает, что (операция на группе является также операцией на множестве .

Знакомство с примерами начнем с подгрупп группы по сложению. Для натурального обозначим через множество всех чисел, кратных как положительных, так и отрицательных. Является ли подгруппой в Для начала отметим, что сумма чисел, кратных тоже кратна так что условие (1) выполнено. Единичным элементом группы служит 0, кратный любому числу, поэтому Наконец, Поэтому обратный к каждому элементу из тоже принадлежит Таким образом, действительно подгруппа в Этот пример вновь появится в § 9.8.

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

чисел С. Если же рассматривать умножение, то множество ненулевых рациональных чисел — подгруппа в которая является подгруппой в

С другой стороны, (группа по умножению) лежит внутри (группы по сложению). Несмотря на это, мы не можем называть подгруппой в поскольку на них определены разные операции.

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

Теорема Лагранжа. Порядок любой подгруппы конечной группы делит порядок всей группы.

Проясним, о чем говорит теорема Лагранжа и, в особенности, чего она не утверждает. Пусть подмножество конечной группы Тогда, очевидно, количество элементов в не больше, чем в (равно, если ). Теорема Лагранжа говорит, что если, к тому же, подгруппа в то порядок обязан делить порядок Это несколько ограничивает круг подмножеств, которые могут являться подгруппами. Однако не верно, что для любого делителя к порядка конечной группы найдется подгруппа в из к элементов.

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

треугольника, порядок которой равен 6. По теореме Лагранжа список порядков ее подгрупп ограничивается числами: 1, 2, 3 и 6. Любая подгруппа должна содержать единичный элемент но это не исключает возможности, что какая-то подгруппа состоит только из него. Таким образом, в есть подгруппа порядка 1. Далее, подгруппа может совпадать со всей группой при этом, естественно, ее порядок будет равен 6. Нам осталось решить задачу о выделении подгрупп в порядков 2 и 3. Это будет сделано после следующего параграфа, где мы исследуем систематический подход к поиску подгрупп.

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