Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 29
Текст из файла (страница 29)
Непосредстпенная проверка выполнения свойств «олька. Теорема 3.2.2. У)гнугееой ыемеит з логьца 2)(д) обратим оттките ьно умножении глогда и малько тогда когда з и и д гзаимяе До«азатегьстео. Пусть з — такой ненулевой элемент кольца, чта г и д взаимна просты. Тогда согласно следствию 2.6.4 найдугся целые числа а и Ь, такие, что ! = ад -1- Ьз.
По модулю соответственно имеем о модулю д 1 = Да[1) = Кг[ад фьз) =Аз[Де[ад) [-Кч[уз[) = = К, (ьз[ =. К, (К,[Ы И, ЕО) = К, [Д, [Ы [ Следовательно, относительно умножения по модулю д мультипли. кативный обратный к з равен Д,[ь Е Пусть теперь з такой элемент кольца, что з и д не взаимно просты. Сначала рассмотрим случай, «агда з делит ф д == з г. Пусть у элемента з есть обратный з '. Тогда г = й,[с[= К,[ы' з г1 =-Дз[х г 41=-0. Но г -ь О [пюб д), так что получаеы противоречие. Таким образом, если г является делителем д, то он не имеет обратного Теперь рассмотрим случай, «огда г и д не нзаимио просты, но в не делит д.
Пусть д =- ИОД [г, д). Тогда з = Ж' для неко. торого з', взаимно простого с д, и делителя д числа д. Если эле мент з обратим, то н элемент д танже обратим: д ' = Мзг', что противоречит толька что доказанааму утверждению. Следова. тельна, г не может быть обратиммм, и теорема доказана.
Поскольку обращение в кольце 2((р) воамоагна не всегда, то в аб~гтем случае ненулевые элементы кольца 2Кр) группы но умножению не образуют. Однано в лДр) можно найти подмно. жества. образующие подгруппы. Выберем в кольце 2)(р) ненуле- вой элемент 5 н сформируем подмножество (5. ()з, ..., р' — 1*~, остановив процесс, кзк только получим единичный элемент Мы уже видели, ~то единичный элемент вжгда дотнжнм и что конструкпия привозят к ииклической группе. Она является под- группой кольна лйр), и целое число г называется порядком эле. мента !) в ЯР) Мы уже видели в примерах разл 23, что арифметика полей ОР (2) н ОГ (3) может быть заданв как сложение и умножение па модулю 2 н 3 соответственна, но арифметика поля 6Р (4) так описана уже быть не ыожет В символической ззпнсн 6Р (2) =- — 27(2), 6Р (3) =- ГДЗ), ОР (!) чь 27(4). Общий РезУльтат онн. сывается следующей теоремой.
Теорема 5.2, 3. Колот!о змчггл з 2((р) лзглетсл поггм глжда и толока тогда, когда р разно лроотолу числу. Доказательство. Предположим, что р проста, Тогда кавщый элемент кольца 2Кр) взаимно прост с р в, следовательно (по теореме 5.2.2), абрагам отнаснтельна умножения Предположим теперь, что р составное число. Тогда р . †. г з и согласно теореме 5.2.2, г н г не могут иметь обратима элемен- тов.Д Если кольцо вычетов 2Др) является полем, то чтобы подчерк- нуть этот факт, оно обозначается через 6Р (р) Коаечные поля, построенные как кольца вьтетов целых чисел, ие исчерпывают всего множества полей, но конечные поля с простым числом эле. ментов нсегпа иогут быть построены как кольца вычетов. Если поле 6Р (р) не содержит «вадратнога корня из — 1, то его можно расширить до ОР (р') точна такии жс способом, как ' поле вещественных чисел расшнряетсв до поля комплексных чи- сел.
Например, в поле 6Р (7) выполняется равенство б =. — 1, но, иак легко проверить, поле не содержит э.чемента, квацрат которого равен 5. Следовательно, поле ОР (49) можно задать множеством элементов вида 6Р(491 = (о -с )3: о, У СОР(7)), определив на нем операции сложения и умножения так же, как, для коыплексных часел: (о 1- )б) -1- (с 1 )д) = (о -1- с) -1- 1 (Ь -1 д), (о з )Н (с -1- (д) = (ас — Ьд) У 1 (ов Р сд), где во всех скобках справа операшги обозначают сложение н умножение в поле 6Р (7) При таком определении множества ОР (49) является полем Целыми паля ОР (49) являются элементы паля ОР (7), так чта.
характеристика поля 6Р (49) раааа 7. Теорема 5.2.4, Каждое лоле содержит однозначно олредггяе. иое ноиленьшге подполе, го орое либо изоморфно гюлю рилиснож. яыг чисел, либо содержит яанеч ое чигго згемгнтог. Стдозотггьно, гар ктеригтика каждого повн Гогуо . бо бегконе но, либо розно и ростову чис,гу. Доютзанмлжтго Каждое пале содержит 0 и 1 Для построения под юля рассмотрим повмножество 6 = 10, 1, 1-г 1, 1-1-! -'; -1- 1, . ), обозначая его элементы соответственно (О, 1, 2, 3, Эта подмножество содержит либо бесконечное множества эле. ментов, либо конечное множество, скажем р т!ы покажеы, что если эта число конечно, то оно просто и 6 — - ОР (р).
Так как 6 является пиклической группой, то сложением в нем служит ело. жение па маиулю р. В силу наличия в поле днстрнбушивнага ю. кана умножение в 6 также являегсв умножением по модулю р, так нак а.й = (1 + 1 -1- .. -1 1) () = 2 -1- 2 -1- ... -,' где суима содержит а копий элемента 5 и сложение выполняется как сложение па молулю р Следовательно, умножение танже яе.
ляется уывожсннем по модулю р Относительна умножения кажлый ненулевой элемент й имеет обратный. таи как послелователь. ность (), 25, 35, ... образует в 6 цннличсскую подгруппу. Поскольку и () ~ 0 для любых ненулевых х и !) нз исходного ° олп, то ад чь О по модулю р для всех целил поля, и, следовательно, р должно быть простмм.
Таким образом, полмвожества 6 образует в точности простое поле, описываемое теоремой 5 2.3. Лльтернативныы является случай, когда множес~во 6 Овско. печно. В этом случае оно изоморфна кольцу целых чисел Нанмень. шее содержащее 6 подполе Р изочорфна наименьшему нолю, содержащему кольна целых чисел, каковым является поле рацио. нальных чисел. С) В поле Галуа ОР (р) всегда можно нзйти простое полполе 6Р (р). В частности, если то р, с которога иы начинаем, само является простим числом, то это простое подполе можно интерпретировать как поле вычетов целых чисел по модулю р Следовательно, на самом деле имеется тольно адво пале с заданным числом элементов, которое, конечно, допускает много различных представлений. 3.3. Поля, осиопаниые ив кольцах миогочлеиов Полл можно строить, оттялкнвзягь т ~голегг мпогачтенов.
такимжеабра м, а~ бы. о ре~ ое~ е л з глп целик чисел. Такая конструкция привалит как и иовечаыи, так н к бесконечнылт полям н зависгглгасти ог того, была ли исходное кольца многачлеаов определена нал конечным илн бесконечным полем Зти расгггггреггл~я охззались полезными в несиальких направлениях дискретной обработки сигналов Они были ис~гольчованы для построения теоретико-числовых преобразований, расслгзтриваемых в гл б, и для настроения алгоритмов многомерной свертки, рассматриваемых в гл 7 Пусть имеется кольца многачленов Г (х! над полем Г Так же каи для кольца Д были построены ковьца вычетов, можно ио. строить и вля кольца Г (х! ега факторкальцо.
Выбирая иа Г !х! произвольный иногачлев р (х), можно определить тапсе кольцо, используя р (х) в качестве ыодуля для задания зрнфметяин *~ага кольца Мы р чнм рн и тр ня т ж, нр нея и ы н ного чланами, так как зто ограаичение снимает ненужную неапреде. лениасть но троеная. Определение 3.3.1. Для произволыюга приведенного многа. члена р (х) ненулевой ггепени нзд полем Г коленом мнагагыеиоз ио модулю р (х) называется множество всех многачленов над Г, степень которых не превосходит степени мнагочлена р (х), с операциями сяожеаия и чииожеияя многачленов по модулю р (х).
Зта кольца принято обощачать через Г (х)Др (х)) Произвольный миогачлен г (х) ив Г' (х ! можно отобразить в Г' (х)((р (х)), соображая г (х) в К,г ~ )г (х)!. Двз сравнимых па модулю р (х) ыемевта а (х) и Ь (х) из Г (х) отображаютсв в один и тот же многачлен нз Г (х)Г(Р (х)). Теорема 3.3.2. Кольца миагочзеиае ио модулю р (х) язхяаю:л кальцом. Даказаюеюсюза Доказательства провоцится прямой проверкой выполнении свойств вальда О В качестве примера рассиотрим кольцо многочленов над ОГ (2), выбирая модуль рваным р (х) =. х* .1- 1. Тогда кольцо многочленов но модулю р (х) равно бу (2) !х)г(йд + 1). Оио состоит из эло лгентов (О, 1, х, х — 1, л, х' -1- 1, х' + к, х' ф х !.
1,! и умно- женке в эталг копыте выполняетсн, например, следуюгцнм образом: (х'-1-1) (х'1 уме~((х' 1-!)х')=ум.л~!х(с' —; 1).с х' !.х)= к'+ х, где использована редукция по правилу х' -= х (х' 1 Ц '- х. ~зг В качестве другого примера рассмотрилг кольцо много~левов над полем рациональных чисел О, выбнраи р (х) - х' е 1. Тогда копыто многочленов по модулю р (х) есть (, !х!Дх* е 1) Оно содержит мнагочлены вива а ; хб, где а и Ь вЂ” рзпиавальные числа Умножение выполняется па правилу (а .1 хЬ) (с .1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
