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

§ 9.8. Теорема Лагранжа

Напомним формулировку теоремы.

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

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

где у — обратный к у элемент группы. В этом случае мы пишем .

Сравнение по модулю определенное в главе 5, является частным случаем этого отношения. Действительно, пусть

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

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

Рефлексивность. Нам нужно показать, что . По определению сравнения это равносильно условию: которое, в свою очередь, следует из тех фактов, что и подгруппа.

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

Транзитивность. Допустим, . Эти сравнения переписываются в виде: соответственно. Так как подгруппа, то

Отсюда , и последнее свойство доказано.

Итак, сравнение по модулю рефлексивно, симметрично и транзитивно, поэтому оно является отношением эквивалентности. Заметим, что существует точное соответствие между условием « подгруппа в и свойствами, которые превращают сравнение по модулю в отношение эквивалентности. Теорема Лагранжа зависит от тонкого баланса всех этих фактов.

Теперь, зная, что сравнение по модулю задает отношение эквивалентности, найдем класс эквивалентности элемента

относительно этого отношения. По определению искомый класс равен

Но условие это то же самое, что Поэтому для некоторого элемента Следовательно, класс эквивалентности элемента х может быть переписан в виде:

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

Доказательство теоремы Лагранжа. Пусть конечная группа с операцией — ее подгруппа. Подсчитаем сначала количество элементов в классе эквивалентности по модулю Я. Если то его класс эквивалентности совпадает с

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

где х, как всегда в этой книге, обозначает обратный элемент к х. Это означает, что различные элементы подгруппы Н при умножении их справа на х дают различные элементы в Итак, мы доказали, что число элементов любого класса совпадает с порядком подгруппы !

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

Последний комментарий. Как мы отмечали в § 9.5, утверждение, обратное теореме Лагранжа, ложно. Точнее, если группа порядка пик — один из делителей числа то группа вовсе не обязана иметь подгруппу порядка к. Например, порядок группы симметрий правильного тетраэдра равен 12, однако в ней нет подгруппы порядка 6. Для доказательства этого факта см. упражнения 20, 21 и 22. Тем не менее, если простой делитель порядка группы, то в непременно найдется подгруппа порядка к. Это утверждение, называемое теоремой Коши (Cauchy), доказано, например, в [45] ([Д.5]).

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

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