Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 216
Текст из файла (страница 216)
Существование единицы: существует элемент е е Я, называемый единзгчным (Ыеш(гу) элементом группы, такой, что е щ а = а ~Э е = а для всех а е Я. 3. Ассоциативность: для всех а, Ь, с е,э" выполняется (а Ю Ь) Ю с = а 6) (Ь ® с). Глава 3!. Теоретико-чиеловне алгоритмы 9о3 В качестве примера рассмотрим уже знакомую нам группу Щ, +) целых чисел Х с операцией сложения; ее единичный элемент — О, а обратный элемент к любому числу а — число — а.
Если группа (Я, !й) обладает свойством каимутатнвностн (соплив!абче !аж) а еэ 6 = 6 ~Ь а для всех а, Ь Е Я, то это абелевв группа (аЬейап йтопр). Если группа (Я, ®) удовлетворяет условию [о] < со, т.е. количество ее элементов конечно, то она называется конечной (Йпйе йтопр). Группы, определяемые саожением н умножением по модулю С помощью операций сложения и умножения по модулю и, где и — положительное целое число, можно образовать две конечные абелевы группы. Эти группы основаны на классах эквивалентности целых чисел по модулю и, определенных в разделе 31.1. Чтобы определить группу над е,„, нужно задать подходящие бинарные операции, полученные путем переопределения обычных операций сложения и умножения. Операции сложения и умножения для е.„определить легко, поскольку классы эквивалентности двух целых чисел однозначно определяют класс эквивалентности их суммы или произведения.
Другими словами, если а г— н а' (шое( и) и 6 гв 6' (шов) и), то а + Ь = а' + 6' (пюб и), аЬ= аЬ (шог( и) . Таким образом, мы определяем сложение и умножение по модулю и, обозначае- мые как +„и .„, следующим образом: [а]„+„[Ь]„= [а+ Ь]„, [а]„„[Ь]„= [аЬ]„. (31 1а) (Вычитание для Ж„можно легко определить по аналогии, как [а]„— „[6]„= [а — Ь]„, однако с делением, как мы сможем вскоре убедиться, дело обстоит сложнее.) Зти факты подтверждают удобную общепринятую практику использования наименьшего неотрицательного элемента каждого класса эквивалентности как представительного при вычислениях в е.о.
Сложение, вычитание и умножение представителей классов выполняется как обычно, но затем каждый результат х заменяется соответствующим представителем его класса эквивалентности (т.е. величиной х пюл( и). На основе определения операции сложения по модулю и определяется адднтнвная группа по модулю и (адд!!1ие ятопр шодп!о и) (е.„, +„). Размер аддитивной группы по модулю и равен [Ж„[ = и. На рис. 31.2,(а) представлены результаты выполнения операций лля группы (Ка, +а).
4. Существование обратного элемента: для каждого а Е Я существует единственный элемент 6 Е Я, называемый обратным (!пиегзе) к а, такой, что а(ВЬ=Ь®а=е. 984 Часть РИ. Избранные темы (6) (ь) Рис. 31.2. Две конечные группы. Классы эквивалентности указаны нх представительными элементами. (в) Группа (Ее, ое), (б) Группа (Е(ь и). Теорема 31.12 Система (Ж„, +„) является конечной абелевой группой. Доказовгевгвсвгвгь Из уравнения (31.18) следует замкнутость (К„, +„).
Ассоциативность и коммутативность +„следует из ассоциативности и коммутативности +: ([а]„+„[Ь]„) +„[с)„= [а + Ь]„+„[с]„ = [(а + Ь) + с)„ = [а+ (6+ с)]„ = [а)„+„[Ь+ с)„ = [а]„+„([6)„+„(с]„), [а]„+„[Ь]„= (а+ Ь]„ = [Ь+ а]„ = [Ь]„+„[а)н . Единичным элементом (.'Е„, +„) является О (т.е.
[О]„). Элементом, (адаптивно) обратным к элементу а (т.е. к [а]„), является элемент — а (т.е. [ — а]„илн (и — а]„), поскольку [а]„+„[ — а]„= [а — а]„= [О]„. На основе операции умножения по модулю и определяется мулввзинликоогивноя группо но модулю тв (пшййр1гсайче 8топр люди!о и) (Ж„', „). Элементы этой группы образуют множество в.„', образованное из элементов множества Е„, взаимно простых с п, так что каждый из них имеет единственный обратный к нему элемент по модулю гк Е'„= ([а) н Е Жн: 8сг)(а, п) = 1) Рл5 Глава 5!. Теоретило-числовые алгоритмы Чтобы убедиться в том, что группа Х*„вполне определена, заметим, что для 0 ( а < и при всех целых lс выполняется соотношение а = (а + )сп) (шос) и). Поэтому из ксс((а, и) = 1 согласно результатам упр.
31.2.3 для всех целых й следует, что кос((а + йп, п) = 1. Поскольку [а]„= (а+ йп: и е е.), множество е.„' вполне определено. Примером такой группы является множество Е,"з — — (1, 2, 4„7, 8, 11, 13, 14), в качестве групповой операции в которой выступает операция умножения по модулю 15. (Здесь элемент [а] ш обозначается как а; например, элемент [7] ьз обозначается как 7.) На рис. 31.2,(б) показана группа (е.ш, сз).
Например, 8 11 = 13 (пюс1 15). Единичным элементом в этой группе является 1. Теорема 31.13 Система (е,'„, „) является конечной абелевой группой. Доказавеельсвево. Из теоремы 31.6 вытекает замкнутость (Ж„',.„). Ассоциативность и коммутативность можно доказать для „так же, как это было сделано для +„в доказательстве теоремы 31.12. Единичным элементом является [1]„. Чтобы показать существование обратных элементов, предположим, что а является элементом е,*„, а процедура Ехтнчпнп-Е15о.цэ(а,п) возвращает (с(,х,р).
Тогда е( = 1, поскольку а Е е.„', и (31. 19) ах+ил = 1 или, что эквивалентно, ах = 1 (шос( п) Таким образом, [х]„является мультипликативным обратным к [а]„по модулю п. Кроме того, [х]„Е Ж„". Чтобы увидеть, почему это так, заметим, что (3!.19) указывает, что наименьшая положительная линейная комбинация х и п должна быть равна 1. Следовательно, из теоремы 31.2 вытекает, что 8сс((х, п) = 1. Доказательство того, что обратные элементы определяются однозначно, отложим до рассмотрения следствия 31.26.
В качестве примера вычисления мультипликативных обратных элементов рассмотрим случай а = 5 и п = 11. Процедура Ехтнмпнп-Еисщп(а, п) возвращает (с(, х, 9) = (1, — 2, 1), так что 1 = 5 ( — 2) + 11 1. Таким образом, [ — 2]ы (те. [9] ы) является мультипликативным обратным к [5]ы.
Далее, в оставшейся части этой главы, когда речь будет идти о группах (е.„, +„) и (.'Е„*, „), мы будем следовать обычной удобной практике обозначения классов эквивалентности представляющими их элементами, а операций +„ и .„— знаками обычных арифметических операций + и (последний знак может опускаться, так что аб = а 5) соответственно. Кроме того, эквивалентность по модулю п можно интерпретировать как равенство в е.„. Например, оба выражения, 986 Часть еП.
Иэбранные тены приведенные ниже, обозначают одно и то же: ах о— а Ь (шоо и), [а[„„[х[„= [Ь[„. Для дальнейшего удобства иногда группа (Я, ®) будет обозначаться просто как Я, а из контекста будет понятно, какая именно операция подразумевается. Таким образом, ~руины (У.„, +„) и (Х„', „) будут обозначаться как Ут и К„' соответственно. Элемент, обратный (относительно умножения) к элементу а, будет обозначаться как (а ' шод и). Операция деления в группе К„' определяется уравнением а/Ь = аЬ ' (шос( и). Например, в Ж;б мы имеем 7 ' = 13 (шос( 15), поскольку 7 13 = 91 = 1 (шод 15), так что 4/7 ги 4 13 ги 7 (шоб 15). Обозначим размер У.'„как ф(и).
Эта функция, известная как ф-функция Эйлера, удовлетворяет уравнению (31.20) р: р протее и р ) н где индекс р пробегает значения всех простых делителей числа и (включая само и, если оно простое). Здесь мы не станем доказывать эту формулу, а попробуем дать для нее интуитивно понятное пояснение. Выпишем все возможные остатки от деления на и — (О, 1,..., и — 1), а затем для каждого простого делителя р числа и вычеркнем из этого списка все элементы, кратные р. Например, простые делители числа 45 — числа 3 и 5, поэтому ф(45) = 45 (1 — -) (1 — -) = 45 (-) (-) = 24. Если р — простое число, то Жр — — (1, 2,..., р — Ц, и Ф(р) = р 1 —— (31.21) = р - 1 Если и — составное, то ф(и) < и — 1; можно показать, что (31.22) ф(и) ) ет 1п 1п и + 1н 1„— „- Глава ЗГ Теоретико-числовые алгоритиы 987 для и > 3, где 7 = 0.5772156649...
— константа Эйлера. Немного более про- стая (и более неточная) нижняя 7раница для и > 5 имеет вид и 61п1пи (31.23) Нижняя граница (31.22), по сути, является наилучшей возможной, поскольку 1пп !и! ф(и) — 7 и-к и/1п1пи (31.24) Подгруппы Если (Я,Ю) является группой, У С Я и (У, !9) также является группой, то (У, Ю) представляет собой подгруппу (Я, Ю). Например, четные целые числа образуют подгруппу целых чисел относительно операции сложения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
