Теорема Лагранжа

Пусть g = (G, ⋅, 1) — группа, а, Н = H, ⋅, 1) — ее подгруппа.

Левым смежным классом подгруппы H по элементу а ∈ G называют множество

аН = {у: у = a ⋅ h, h ∈ Н}.

Соответственно правый смежный класс подгруппы Н по элементу a ∈ G — это множество

На = {у: у = h ⋅ a, h ∈ H}.

Очевидно, что в коммутативной группе аН = На.

Замечание. При использовании аддитивной записи групповой операции смежные классы записываются в виде а + Н (или H + а). #

Рассмотрим левые смежные классы. Прежде всего заметим, что если а ∈ Н, то аН = H. Действительно, если х ∈ аН, то для некоторого h ∈ H  х = ah, а так как a ∈ H и множество H замкнуто относительно умножения группы g, то х ∈ H. Обратно, если х ∈ H, то х = аа^-1 = аh, где h = а^-1x ∈ H. Поэтому х ∈ aH. Окончательно получим H = аH.

Введем теперь бинарное отношение ~_H на множестве G следующим образом: элементы а и b связаны отношением ~_H (а~_Hb), если и только если левые смежные классы подгруппы H по элементам а и b совпадают (аН = bH).

Теорема 2.11. Бинарное отношение ~_H есть эквивалентность на G, причем класс эквивалентности произвольного элемента a∈G совпадает с левым смежным классом аН.

◀Докажем, что ~_H является эквивалентностью на G. Поскольку аН = аН для любого а ∈ G, т.е. а~_Ha, то бинарное отношение ~_H рефлексивно. Если а~_Hb, то aH = bH, следовательно, bH = аH и b~_Ha, т.е. бинарное отношение ~_H симметрично. Наконец, из того, что а~_Hb и b~_Hс, следует аH = bH и bH = сH, т.е. аН = сH и а~_Hс> откуда вытекает, что бинарное отношение ~_H транзитивно. Итак, ~_H есть эквивалентность.

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

Пусть х ∈ [а]~_H, т.е. x~_Hа, тогда хН = аН. Последнее означает, что любой элемент вида ah, h ∈ H, может быть представлен в виде xh₁ где h₁ ∈ H, т.е. ah = xh₁. Отсюда получаем х = ahh^-11. Поскольку H - подгруппа, h, h₁ ∈ H, то h₂ = hh^-11∈ H. Следовательно, x = ah₂ ∈ aH и [а]~_H ⊆ aH.

Покажем второе включение, т.е. докажем, что аН ⊆ [а]~_H. Пусть х ∈ аН, тогда х = ah для некоторого h ∈ Н. Отсюда получаем, что xH = ahH. Поскольку для всякого h ∈ H, как доказано выше, xH = H, справедливо равенство хН = аH, откуда х~_Hа и x ∈ [а]х~_H.▶

Теорема 2.12. Всякий левый смежный класс подгруппы H равномощен Н.

◀Для произвольного фиксированного a ∈ G зададим отображение φ_a: H → aH следующим образом: φ_a(h) = ah. Во-первых, отображение φ_a есть сюръекция, так как если х ∈ аH, то х = ah для некоторого h∈H, откуда x: = φ_a(h). Во-вторых, φ_a — инъекция, поскольку из равенства ah₁ = ah₂ в силу законов сокращения в группе g следует h₁ = h₂. Следовательно, φ_a — биекция и |аH| = |H|. ▶

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

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

◀Согласно теореме 2.11, все левые смежные классы образуют разбиение множества G на подмножества, равномощные в силу теоремы 2.12 подгруппе Н. Так как группа g конечна, то число элементов разбиения конечно. Обозначив это число через k, заключаем, что |G| = k|H|. Следовательно, порядок группы |G| делится на порядок группы |H|. ▶

Число всех левых смежных классов подгруппы H конечной группы g называют левым индексом подгруппы Н в группе g.

Рассмотрим некоторые следствия теоремы Лагранжа.

Следствие 2.3. Любая группа простого порядка является циклической.

◀Возьмем в группе, порядок которой есть простое число, какую-то ее циклическую подгруппу, образующий элемент которой отличен от единицы (нейтрального элемента) группы. Тогда эта подгруппа содержит не менее двух элементов и ее порядок, согласно теореме Лагранжа, должен быть делителем порядка группы. Поскольку порядок всей группы — простое число, а порядок подгруппы не меньше 2, то он совпадет с порядком всей группы. ▶

Замечание. Группа, порядок которой не является простым числом, может быть циклической, т.е. утверждение, обратное следствию 2.3, не имеет места. Так, например, циклической является ℤ⁺⁴ — аддитивная группа вычетов по модулю 4. Ее образующий элемент — 1. Можно доказать, например, что любая группа порядка 15 является циклической*. #

Группу называют неразложимой, если она не имеет нетривиальных подгрупп.

Следствие 2.4. Конечная группа неразложима тогда и только тогда, когда она является циклической группой, поря- порядок которой есть простое число.

◀Если группа циклическая и ее порядок — простое число, то, согласно теореме Лагранжа, каждая ее подгруппа имеет порядок, равный либо единице, либо порядку всей группы, и группа неразложима.

Обратно, пусть конечная группа g = (G, ⋅, 1) неразложима. Покажем, что |G| — простое число. Выберем элемент а ≠ 1. Тогда циклическая подгруппа с образующим элементом о совпадает с g. Допустим, что |G| — составное число, т.е. |G| = = kl для некоторых натуральных k и l, отличных от 1 и |G|. Тогда циклическая подгруппа с образующим элементом b = а^k не совпадает с g, так как b¹ = a^kl = 1 и в этой подгруппе не более l элементов, что противоречит неразложимости группы g. Следовательно, порядок группы g есть простое число. ▶

Следствие 2.5. В конечной группе g для любого элемента a ∈ G имеет место равенство a^|G| = 1.

◀Если группа g циклическая и элемент a — ее образующий элемент, утверждение очевидно. Если же элемент а является образующим элементом некоторой циклической подгруппы группы g порядка k < |G|, то в силу теоремы Лагранжа |G| = kl для некоторого натурального l. Отсюда получаем a^|G|= a^kl = (а^k)^l = 1^l = 1. ▶

С помощью теоремы Лагранжа (точнее, следствия 2.5) можно доказать, что если целое число n не делится на простое число р, то n^p-1 - 1 делится на р. В теории чисел это утверждение известно как малая теорема Ферма.

Действительно, пусть n = rр + k, где r — целое, а 0 < k < р (остаток от деления n на р). Тогда ясно, что n^p-1 = к^p-1 (modp) (достаточно разложить (гр + k)^p-1 по формуле бинома Ньютона). Рассмотрим группу ℤ^*p (мультипликативную группу вычетов по модулю р) и в этой группе элемент k. Порядок группы ℤ^*p = р — 1. Если k = 1, то

n^p-1 - 1 = (1^p-1 - 1) (modp) = 0 (modp)

и утверждение очевидно. Согласно следствию 2.5, в группе ℤ^*p справедливо равенство k^p-1 = 1, т.е. k^p-1 = 1(modp), и, следовательно, к^p-1 - 1 = 0(modp), т.е. число k^p-1 равно 1 по модулю р. Поэтому n^p-1= k^p-1 = 1 (modp).

Малая теорема Ферма дает возможность доказывать утверждения о делимости очень больших чисел. Например, из нее следует, что при р = 97 число 97 является делителем n⁹⁶ — 1 для любого n, не делящегося на 97. Подобного рода заключения важны при разработке алгоритмов защиты информации.

Кроме того, используя малую теорему Ферма, можно вычислять в полях вычетов по модулю р (р — простое число) элементы, обратные к заданным относительно умножения. Действительно, если a ∈ ℤ_p, то, так как а^p-1 = 1, умножая последнее равенство на а^-1, получим а^p-1 =а^-1. Таким образом, для того чтобы вычислить элемент, обратный к а по умножению, достаточно возвести его в степень р - 2 или, что равносильно, в степень, равную остатку от деления числа р - 2 на порядок циклической подгруппы группы ℤ^*p  , порожденной элементом а (см. теорему 2.7).

Пример 2.20. Рассмотрим, как вычислить элемент, обратный к а по умножению в поле ℤ₁₇. Согласно полученному выше результату, для вычисления обратного к а элемента нужно найти а^17-2 = а¹⁵. Однако объем вычислений можно сократить, если порядок циклической подгруппы, порожденной элементом а, меньше порядка группы.

Порядок группы ℤ^*17   равен 16, следовательно, порядок циклической подгруппы, порожденной элементом а, может составлять, согласно теореме Лагранжа, 2, 4, 8, 16 (т.е. быть каким-то из делителей числа 16). Поэтому при поиске обратного элемента достаточно проверить следующие степени а (кроме 15-й): 1 (остаток от деления 15 на 2), 3 (остаток от деления 15 на 4) и 7 (остаток от деления 15 на 8).

Найдем элемент, обратный к 2. Очевидно, что 2^-1 ≠ 2, так как 2 ⨀₁₇ 2 = 4 ≠ 1. Далее получим 2³ = 4 ⨀₁₇ 2 = 8. Поскольку 2 ⨀₁₇ 8 = 16 ≠ 1, то 2³ = 8 также не является обратным к 2. Вычислим 2⁷ = 2³ ⨀₁₇³ ⨀₁₇ 2 = 8 ⨀₁₇ 8 ⨀₁₇ 2 = 9. Поскольку 9 ⨀₁₇ 2 = 1, в итоге получаем 2^-1 = 9.

Найдем элемент, обратный к 14. Так как 14 ⨀₁₇ 14 = 9, то 14^-1 ≠ 14. Вычисляем 14³ = 14 ⨀₁₇ 9 = 7, но 14 ⨀₁₇ 7 = 13, т.е. 14³≠ 14^-1. Далее,

14⁷ = 14³ ⨀₁₇ 14⁴ = 7 ⨀₁₇ 13 = 6,

14 ⨀₁₇ 6 = 16 = -1.

Мы видим, что и 14⁷ ≠ 14^-1. Следовательно, остается вычислить 14^-1 = 14¹⁵. Однако в этом случае вычисления можно сократить, заметив, что 14 ⨀₁₇ 14⁷ = 14 ⨀₁₇ 6 = -1. Из последнего равенства, согласно следствию 2.1, получим

1 = 14⨀₁₇ (-6) = 14⨀₁₇ 11,

откуда 14^-1 = 11.

Отметим, что 14¹⁶ = 1, т.е. порядок циклической подгруппы, порожденной элементом 14, совпадает с порядком всей группы ℤ^*17  , и, следовательно, эта группа является циклической, порожденной элементом 14 (хотя и не только им).