Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Теорема Лагранжа о порядке конечной группы

Теорема Лагранжа о порядке конечной группы


Пусть [math]\mathcal{G}=(G,\cdot,\bold{1})[/math] — группа, [math]\mathcal{H}= (H,\cdot, \bold{1})[/math] — ее подгруппа. Левым смежным классом подгруппы [math]\mathcal{H}[/math] по элементу [math]a\in G[/math] называют множество


[math]aH=\bigl\{y\colon\, y=a\cdot h,~ h\in H\bigr\}.[/math]

Соответственно правый смежный класс подгруппы [math]\mathcal{H}[/math] по элементу [math]a\in G[/math] — это множество


[math]Ha= \bigl\{y\colon\, y=h\colon a,~ h\in H\bigr\}.[/math]

Очевидно, что в коммутативной групп [math]aH=Ha[/math].


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


Рассмотрим левые смежные классы. Прежде всего заметим, что если [math]a\in H[/math], то [math]aH=H[/math]. Действительно, если [math]x\in aH[/math], то для некоторого [math]h\in H[/math] имеем [math]x=ah[/math], а так как [math]a\in H[/math] и множество [math]H[/math] замкнуто относительно умножения группы [math]\mathcal{G}[/math], то [math]x\in H[/math]. Обратно, если [math]x\in H[/math], то [math]x=aa^{-1}x=ah[/math], где [math]h=a^{-1}x\in H[/math]. Поэтому [math]x\in aH[/math]. Окончательно получим [math]H=aH[/math].


Введем теперь бинарное отношение [math]\sim_{H}[/math] на множестве [math]G[/math] следующим образом: элементы [math]a[/math] и [math]b[/math] связаны отношением [math]\sim_{H}[/math] [math](a\sim_{H}b)[/math], если и только если левые смежные классы подгруппы [math]\mathcal{H}[/math] по элементам [math]a[/math] и [math]b[/math] совпадают [math](aH=bH)[/math].




Теорема 2.11. Бинарное отношение [math]\sim_{H}[/math] есть эквивалентность на [math]G[/math], причем класс эквивалентности произвольного элемента [math]a\in G[/math] совпадает с левым смежным классом [math]aH[/math].


Докажем, что [math]\sim_{H}[/math] является эквивалентностью на [math]G[/math]. Поскольку [math]aH=aH[/math] для любого [math]a\in G[/math], то есть [math]a\sim_{H}a[/math], то бинарное отношение [math]\sim_{H}[/math] рефлексивно. Если [math]a\sim_{H}b[/math], то [math]aH=bH[/math], следовательно, [math]bH=aH[/math] и [math]b\sim_{H}a[/math], т.е. бинарное отношение [math]\sim_{H}[/math] симметрично. Наконец, из того, что [math]a\sim_{H}b[/math] и [math]b\sim_{H}c[/math] следует [math]aH=bH[/math] и [math]bH=cH[/math], т.е. [math]aH=cH[/math] и [math]a\sim_{H}c[/math], откуда вытекает, что бинарное отношение [math]\sim_{H}[/math] транзитивно. Итак, [math]\sim_{H}[/math] есть эквивалентность.


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


Пусть [math]x\in[a]_{\sim_{H}}[/math], то есть [math]x\sim_{H}a[/math], тогда [math]xH=aH[/math]. Последнее означает, что любой элемент вида [math]ah,~ h\in H[/math], может быть представлен в виде [math]xh_1[/math], где [math]h_1\in H[/math], т.е. [math]ah=xh_1[/math]. Отсюда получаем [math]x=ahh_1^{-1}[/math]. Поскольку [math]\mathcal{H}[/math] — подгруппа, [math]h,h_1\in H[/math], то [math]h_2=hh_1^{-1}\in H[/math]. Следовательно, [math]x=ah_2\in aH[/math] и [math][a]_{\sim_{H}}\subseteq aH[/math].


Покажем второе включение, т.е. докажем, что [math]aH\subseteq [a]_{\sim_{H}}[/math]. Пусть [math]x\in aH[/math], тогда [math]x=ah[/math] для некоторого [math]h\in H[/math]. Отсюда получаем, что [math]xH=ahH[/math]. Поскольку для всякого [math]h\in H[/math], как доказано выше, [math]hH=H[/math], справедливо равенство [math]xH=aH[/math], откуда [math]x\sim_{H}a[/math] и [math]x\in[a]_{\sim_{H}}[/math].




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


Для произвольного фиксированного [math]a\in G[/math] зададим отображение [math]\varphi_{a} \colon H\to aH[/math] следующим образом: [math]\varphi_{a}(h)=ah[/math]. Во-первых, отображение [math]\varphi_{a}[/math] есть сюръекция, так как если [math]x\in aH[/math], то [math]x=ah[/math] для некоторого [math]h\in H[/math], откуда [math]x\in\varphi_{a}(h)[/math]. Во-вторых, [math]\varphi_{a}[/math] — инъекция, поскольку из равенства [math]ah_1=ah_2[/math] в силу законов сокращения в группе [math]\mathcal{G}[/math] следует [math]h_1=h_2[/math]. Следовательно, [math]\varphi_{a}[/math] — биекция и [math]|aH|=|H|[/math].


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


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


Согласно теореме 2.11, все левые смежные классы образуют разбиение множества [math]G[/math] на подмножества, равномощные в силу теоремы 2.12 подгруппе [math]H[/math]. Так как группа [math]\mathcal{G}[/math] конечна, то число элементов разбиения конечно. Обозначив это число через [math]k[/math], заключаем, что [math]|G|=k|H|[/math]. Следовательно, порядок группы |G| делится на порядок группы [math]|H|[/math].


Число всех левых смежных классов подгруппы [math]\mathcal{H}[/math] конечной группы [math]\mathcal{G}[/math] называют левым индексом подгруппы [math]\mathcal{H}[/math] в группе [math]\mathcal{G}[/math].




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


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


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


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


Замечание. Группа, порядок которой не является простым числом, может быть циклической, т.е. утверждение, обратное следствию 2.3, не имеет места. Так, например, циклической является [math]\mathbb{Z}_{4}^{+}[/math] — аддитивная группа вычетов по модулю 4. Ее образующий элемент — 1. Можно доказать, например, что любая группа порядка 15 является циклической.


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


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


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


Обратно, пусть конечная группа [math]\mathcal{G}=(G,\cdot,\bold{1})[/math] неразложима. Покажем, что [math]|G|[/math] — простое число. Выберем элемент [math]a\ne\bold{1}[/math]. Тогда циклическая подгруппа с образующим элементом [math]a[/math] совпадает с [math]\mathcal{G}[/math]. Допустим, что [math]|G|[/math] — составное число, т.е. [math]|G|=kl[/math] для некоторых натуральных [math]k[/math] и [math]l[/math], отличных от 1 и [math]|G|[/math]. Тогда циклическая подгруппа с образующим элементом [math]b=a^k[/math] не совпадает с [math]\mathcal{G}[/math], так как [math]b^l=a^{kl}=\bold{1}[/math] и в этой подгруппе не более [math]l[/math] элементов, что противоречит неразложимости группы [math]\mathcal{G}[/math]. Следовательно, порядок группы [math]\mathcal{G}[/math] есть простое число.


Следствие 2.5. В конечной группе [math]\mathcal{G}[/math] для любого элемента [math]a\in G[/math] имеет место равенство [math]a^{|G|}=1[/math].


Если группа [math]\mathcal{G}[/math] циклическая и элемент a — ее образующий элемент, утверждение очевидно. Если же элемент а является образующим элементом некоторой циклической подгруппы группы [math]\mathcal{G}[/math] порядка [math]k<|G|[/math], то в силу теоремы Лагранжа [math]|G|=kl[/math] для некоторого натурального [math]l[/math]. Отсюда получаем


[math]a^{|G|}=a^{kl}= (a^k)^l= \bold{1}^l=\bold{1}\,.[/math]



Малая теорема Ферма


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


Действительно, пусть [math]n=rp+k[/math], где [math]r[/math] — целое, а [math]0<k<p[/math] (остаток от деления [math]n[/math] на [math]p[/math]). Тогда ясно, что [math]n^{p-1}\equiv k^{p-1}\pmod{p}[/math] (достаточно разложить [math](rp+k)^{p-1}[/math] по формуле бинома Ньютона). Рассмотрим группу [math]\mathbb{Z}_p^{\ast}[/math] (мультипликативную группу вычетов по модулю [math]p[/math]) и в этой группе элемент [math]k[/math]. Порядок группы [math]\mathbb{Z}_p^{\ast}=p-1[/math]. Если [math]k=1[/math], то


[math]n^{p-1}-1\equiv (1^{p-1}-1)\pmod{p}\equiv 0\pmod{p}[/math]

и утверждение очевидно. Согласно следствию 2.5, в группе [math]\mathbb{Z}_p^{\ast}[/math] справедливо равенство [math]k^{p-1}=1[/math], то есть [math]k^{p-1}=1\pmod{p}[/math], и, следовательно, [math]k^{p-1}-1=0\pmod{p}[/math], т.е. число [math]k^{p-1}[/math] равно 1 по модулю [math]p[/math]. Поэтому


[math]n^{p-1}= k^{p-1}=1\pmod{p}.[/math]

Малая теорема Ферма дает возможность доказывать утверждения о делимости очень больших чисел. Например, из нее следует, что при [math]p=97[/math] число 97 является делителем [math]n^{96}-1[/math] для любого [math]n[/math], не делящегося на 97. Подобного рода заключения важны при разработке алгоритмов защиты информации.


Кроме того, используя малую теорему Ферма, можно вычислять в полях вычетов по модулю [math]p[/math] ([math]p[/math] — простое число) элементы, обратные к заданным относительно умножения. Действительно, если [math]a\in\mathbb{Z}_p[/math], то, так как [math]a^{p-1}=1[/math], умножая последнее равенство на [math]a^{-1}[/math], получим [math]a^{p-2}= a^{-1}[/math]. Таким образом, для того чтобы вычислить элемент, обратный к [math]a[/math] по умножению, достаточно возвести его в степень [math]p-2[/math] или, что равносильно, в степень, равную остатку от деления числа [math]p-2[/math] на порядок циклической подгруппы группы [math]\mathbb{Z}_p^{\ast}[/math], порожденной элементом [math]a[/math] (см. теорему 2.7).




Пример 2.20. Рассмотрим, как вычислить элемент, обратный к а по умножению в поле [math]\mathbb{Z}_{17}[/math]. Согласно полученному выше результату, для вычисления обратного к а элемента нужно найти [math]a^{17-2}=a^{15}[/math]. Однако объем вычислений можно сократить, если порядок циклической подгруппы, порожденной элементом а, меньше порядка группы.


Порядок группы [math]\mathbb{Z}_{17}^{\ast}[/math] равен 16, следовательно, порядок циклической подгруппы, порожденной элементом а, может составлять, согласно теореме Лагранжа, 2, 4, 8, 16 (т.е. быть каким-то из делителей числа 16). Поэтому при поиске обратного элемента достаточно проверить следующие степени [math]a[/math] (кроме 15-й): 1 (остаток от деления 15 на 2), 3 (остаток от деления 15 на 4) и 7 (остаток от деления 15 на 8).


Найдем элемент, обратный к 2. Очевидно, что [math]2^{-1}\ne2[/math], так как [math]2\odot_{17}2= 4\ne1[/math]. Далее получим [math]2^3=4 \odot_{17}2=8[/math]. Поскольку [math]2\odot_{17}9= 16\ne1[/math], то [math]2^3=8[/math] также не является обратным к 2. Вычислим


[math]2^7=2^3 \odot_{17} 2^3 \odot_{17} 2= 8 \odot_{17} 8 \odot_{17} 2=9.[/math]

Поскольку [math]9 \odot_{17} 2=1[/math], в итоге получаем [math]2^{-1}=9[/math].


Найдем элемент, обратный к 14. Так как [math]14 \odot_{17} 14=9[/math], то [math]14^{-1}\ne14[/math]. Вычисляем [math]14^3=14 \odot_{17} 9=7[/math], но [math]14 \odot_{17} 7=13[/math], то есть [math]14^3\ne14^{-1}[/math]. Далее,


[math]14^7=14^3 \odot_{17} 14^4= 7 \odot_{17} 13=6,\quad 14 \odot_{17} 6=16=-1.[/math]

Мы видим, [math]14^7\ne14^{-1}[/math]. Следовательно, остается вычислить [math]14^{-1}= 14^{15}[/math]. Однако в этом случае вычисления можно сократить, заметив, что [math]14 \odot_{17} 14^7= 14 \odot_{17} 6=-1[/math]. Из последнего равенства, согласно следствию 2.1, получим


[math]1=14 \odot_{17} (-6)= 14 \odot_{17} 11[/math], откуда [math]14^{-1}=11[/math].

Отметим, что [math]14^{16}=1[/math], т.е. порядок циклической подгруппы, порожденной элементом 14, совпадает с порядком всей группы [math]\mathbb{Z}_{17}^{\ast}[/math], и, следовательно, эта группа является циклической, порожденной элементом 14 (хотя и не только им).


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved