XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 25
Текст из файла (страница 25)
1ь Следствие 2.5. В конечной группе й для любого элемента а Е С имеет место равенство а~ ~ = 1. < Если группа й циклическая и элемент а — ее образующий элемент, утверждение очевидно. Если же элемент а является образующим элементом некоторой циклической подгруппы группы й порядка Й < Щ то в силу теоремы Лагранжа ~С~ = Й1 для некоторого натурального 1. Отсюда получаем а~п~ = ам = = (а~) = 1 = 1. ь С помощью теоремы Лагранжа (точнее, следствия 2.5) можно доказать, что если целое число и не делится на простое число р, то пя ~ — 1 делится на р. В теории чисел это утверждение известно как ма.вал теорема Ферма.
Действительно, пусть п = гр+ Й, где г — целое, а 0 < Й < р (остаток от деления анар). Тогдаясно, что пР ~ =ЙР ~(шар) (достаточно разложить (гр+ Й)р ~ по формуле бинома Ньющова). Рассмотрим группу Е„' (мульииимвкатииеную группу 156 2.
АЛГЕБРЫ: ГРУППЫ И КОЛЪЦА вычешоя по модулю р) и в этой группе элемент й. Порядок группы Ер — — р- 1. Если Й = 1, то тР "— 1=(1" ' — 1)(шойр) =0(шеар) и утверждение очевидно. Согласно следствию 2.5, в группе Ер справедливо равенство ля 1 = 1, т.е.
кл ' = 1(шеар), и, следовательно, /Р 1 — 1 = 0(шос)р), т.е. число йя 1 равно 1 по модулю р. Поэтому тР 1 = /Р ~ = 1 (шоб р). Малая теорема Ферма дает возможность доказывать утверждения о делимости очень больших чисел. Например, ю нее следует, что при р = 97 число 97 является делителем пзе — 1 для любого и, не делящегося на 97. Подобного рода заключения важны при разработке алгоритмов защиты информации. Кроме того, используя малую теорему Ферма, можно вычислять в полля вычетов по модулю р (р — простое число) элементы, обратные к заданным относительно умножения.
Действительно, если а Е Ер, то, так как а" = 1, умножая последнее равенство на а 1, получим аг ~ = а 1. Таким образом, для того чтобы вычислить элемент, обратный к а по умножению, достаточно возвести его в степень р — 2 или, что равносильно, в степень, равную остатку от деления числа р — 2 на порядок циклической подгруппы группы Ер, порожденной элементом а (см. теорему 2.7). Пример 2.20. Рассмотрим, как вычислить элемент, обратный к а по умножению в поле Е1ъ Согласно полученному вьппе результату, для вычисления обратного к а элемента нужно найти а17 ~ = а1з. Однако объем вычислений можно сократить, если порядок циклической подгруппы, порожденной элементом а, меньше порядка группы.
Порядок группы Е17 равен 16, следовательно, порядок циклической подгруппы, порожденной элементом а, может составлять, согласно теореме Лагранжа, 2, 4, 8, 16 (т.е. быть каким-то ю делителей числа 16). Поэтому при поиске обратного элемента достаточно проверить следующие степени а (кроме 157 г.В. ГЬ р4в гру 15-й): 1 (остаток от деления 15 на 2), 3 (остаток от деления 15 ' на 4) и 7 (остаток от деления 15 на 8).
Найдем элемент, обратный к 2. Очевидно, что 2 1 ~ 2, так как 2Оп2=4у~1. Далее получим 2 =4О172=8. Поскольку 2 Оп 8 = 16 ф 1, то 2з = 8 также не является обратным к 2. Вычислим 2т = 2з Оп 2з Оп 2 = 8 Оп 8 Оп 2 = 9. Поскольку 9 Оп 2 = 1, в итоге получаем 2 з = 9. Найдем элемент, обратный к 14. Так как 14 Оп 14 = 9, то 14 1 ф 14. Вычисляем 14з = 14 Оы 9 = 7, но 14 Оп 7 =' 13, т.е.
14з ф14 1. Далее, 147 = 14з Оп 144 = 7 Оп 13 = 6, 14 Оп 6 = 16 = -1. Мы видим, что и 147 ~ 14 1. Следовательно, остается вычислить 14 з = 141з. Однако в этом случае вычисления можно сократить, заметив, что 14 Оп 147 = 14 Оп 6 = — 1. Из последнего равенства, согласно следствию 2.1, получим 1 = 14 Оп ( — 6) = 14 Оп 11, откуда 14 1=11. Отметим, что 14зе = 1, т.е.
порядок циклической подгруппы, порожденной элементом 14, совпадает с порядком всей группы Еп, и, следовательно, эта группа является циклической, порожденной элементом 14 (хотя и не только им). 2.8. Гомоморфизмы групп и нормальные делители Пусть заданы группы й1 = (6ь, 1) и 0з = (6з 1). Отображение у: 61-+ 6з называют гомоморфюмом группы Д~ в группу Дз (гомоморфизмом групп), если для любых х, у Е 61 выполняется равенство у(х у) = у(х) у(у), т.е. образ проюведения любых двух элементов группы й1 при овзобрахсении у равен произведению вх образов в группе Дз.
158 2. АЛГЕБРЫ: ГРУППЫ И КОЛЪЦА Если отображение у сюрьентивно (биентивно), то его называют зпиморЯизмом (изоморЯизмом) групп. В этом случае говорят также об эпиморфизме (изоморфюме) группы Д~ на группу йз. Замечание 2.5. Мы обозначили операиии групп Д~ и Дг одинаково, как это обычно и делаетсл для однотипных алгебр, хотя, конечно, это разные операции разных групп.
Пример 2.21. Пусть Д~ = (Е, +, 0) — аддитивнал группа иелых чисел, а Дг = Е~+ — аддитивная группа вычетов по модулю Й. Зададим отображение ~ так: для всякого целого т образ ~(т) равен остатку от деления т на Й. Можно проверить, что для любых целых т и и имеет место равенство у(т+ п) = = у (т) Щ у (и), т.е. для целых чисел остаток от деления суммы на Й равен сумме по модулю Й остатков от деления на Й каждого слагаемого. Следовательно, данное отображение есть гомоморфизм группы Д~ в группу Дг.
Далее, поскольку любое целое число от 0 до Й вЂ” 1 есть остаток от деления на Й какого-то числа, то отображение у является и эпиморфиэмом группы Д~ на группу Дз. Теорема 2.14. Пусть Дп Дг — проюволъные группы. Если ~: Д~ -+ Дг — гомоморфизм, то: 1) образом единииы (нейтрального элемента) группы Д~ при отображении ~ является единица группы Дг, т.е. у (1) = 1; 2) для всякого элемента х группы Д~ образом элемента х ~ являетсл элемент Щх)] ~, обратный элементу ~(х), т.е.
,~(х ~) = [Дх)] '. ч Согласно определению гомоморфизма, для произвольного х Е С~ имеем у(х) . Д1) = у(х. 1). Далее, ~(х 1) = У(х), т.е. у(х) у(1) = у(х). Следовательно, у(1) = (у(х)) ~ у(х) = 1, т.е. У(1) = 1. Докажем второе утверждение теоремы. Используя определение гомоморфюма и уже доказанное первое утверждение 159 2.8.
Гомонорфизны грува теоремы, получаем т.е. Дх ~) = [~(х)] Множество ~(С~) — образ носителя группы Д~ при гомоморфизме у — замкнуто относительно умножения группы Дз. Действительно, если д2, дз' Е ~(Д~), то существуют такие дед~~ е Дм что у(д~) = дз и у(д~~) = дз~. Тогда дздз' = ~(д~) У(д~ ) = у (д~д~ ) Е У(й) Из теоремы 2.14 следует, что ~(Д~) содержит единицу этой группы и вместе с каждым элементом обратный к нему элемент. Это значит, что можно определить подгруппу группы Уз, носителем которой будет множество ДС~).
Эту группу называют гомоморфным образом группы Д~ при гомоморфвзме ~. Группу К называют просто гомоморфным образом группы й, если существует гомоморфвзм группы й на группу К. Так, группа Е„' при любом Й ) 1 является гомоморфным образом аддитивной группы целых чисел (см. пример 2.21). Обратимся к следующему примеру.
Пример 2.22. Рассмотрим мультипликативную группу (С ~ (О),, 1) комплексных чисел с обычной операцией умножения комплексных чисел. Легко понять, что эта группа не что иное, как л4ультипликатпиеная группо полл комплексных чисел. Рассмотрим также группу Мз невырожденных квадратных матриц второго порядка с операцией умножения матриц (см. пример 2.9.е). Определим отображение у множества С комплексных чисел в множество квадратных матриц второго порядка, положив для произвольного ненулевого комплексного числа а+ Ы,что 160 г. ЛПГКВРЫ: ГРУППЫ И КОПЬЦД Покажем, что у — гомоморфизм групп. С одной стороны, Яа+Ь)(с+й)) =1((ас — Ы)+1(аб+Ьс)) = ас — Ы ад+ Ьс1 -аИ- Ьс ас- Ы/ С другой стороны, У(~+ Ь1Ш~+ б1) = Ь а ~ ~ с ас — Ы ад+ Ьс~ -аб — Ьс ас-Ы,/' Следовательно, Д(а+ Ы)(с+ й)) = ~(а+ Ь1) ~(с+ й).
Таким образом, отображение У вЂ” гомоморфизм групп, а гомоморфный образ мультипликативной группы комплексных чисел при ) — это подгруппа К группы матриц Мг, состоящая /а Ь~ из матриц вида ~ (. Здесь мы учли, что любая матри- 1;Ь а) /а Ь~ ца вида ~ ) является образом некоторого комплексного числа (а именно а+Ь1) при отображении у.
Группа 1С вЂ” собственнал подгруппа группы Мг. Сформулируем без доказательства одно важное свойство гомоморфизмов групп. Теорема 2.15. Если у — гомоморфизм группы Д в группу /С, а д — гомоморфиэм группы (С в группу .С, то комнозинил отображени61од есть гомоморфизм группы Д в группу С. ф Рассмотрим некоторые свойства иэоморфизмов групп. Теорема 2.16. Если у: Д~ -+ Дг — изоморфиэм группы Д~ на группу Дг, то отображение у 1, обратное к отображению у, есть изоморфиэм группы Дг на группу 01. 2.8.
Гомоморфизмм груоя 161 ~ Пусть х и у — произвольные элементы группы Дз, пусть также х = Ди), а у = у(е), где и и и — элементы группы Д1. Тогда у 1(ху) =у (Ди))'(е)) =у (Дие)) =пи=у (х)у 1(у), т.е. отображение у 1 — гомоморфизм второй группы в первую.
Но так как отображение, обратное к биекции, есть биекция, то у" 1 — изоморфвзм группы Дг на группу Д1. Ь Группы Д и /С называют изоморфными, если существует иэоморфиэм одной из них на другую. При этом используют обозначение Д о'IС. Изоморфные группы с точки зрения их алгебраических свойств соверщенно одинаковы, хотя их элементы могут иметь различную природу. Вернемся в этой связи к примеру 2.22. Легко убедиться в том, что определенное там отображение ~ множества комплексных чисел на множество квадратных матриц специального вида является биекцией. Следовательно, мультипликативнзя группа комплексных чисел и группа матриц указанного вида с операцией умножения матриц изоморфны, хотя элементы этих групп на первый взгляд не имеют между собой ничего общего.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
