Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 12
Текст из файла (страница 12)
Так как а и Ь оба целые, то они равны ! илп — 1. Положительное целое число р > 1, «отаров делится только па -~р или ~ 1, называется простым. Наименьшими простыми числами являются 2, 3, 5, У, 11, !3, ..., число 1 не является простым. Не являющееся простым положительное целое числа называется составным. Наибамший обций делитель двух целых чисел г и з обозначается НОД (г, з) н определяется как наибол~ шее положительное число, аоторое делит абз из них. Нашгепгшме обичее кратное двух паложителыгых чисел г и ч обозначается НОК (г, г! и определятся как наименьшее положительное число, которое лепится на аба из нкх Деа числа называются гзаимпо арастмми, если зх наибольший общий делитель разов 1.
В кольце целых чисел всегда возможно сокращение; есгщ са — сЬ н с отлично от ауля, то а = Ь. В кольце целых чисел имеется также слабая форма деления, известная под названием деления с остатком или алгоритма деления. З.а. К по цтм«чзс« Теорема 2.6.1 (Алгоритм деления) Для казсдага Легсга числа с и положительного йегага числа й яайдетсл гдиястгеяная пара Легмх чисел г) (частит) и з (остаток), таких чта с = йг) ф з, где б < з < й.
Частное иногда обозначается е- [Я. Обычно нас будет больше интересовать остаток, чем частное. Если з н с при делении на й имеют одни и тот же остаток, то это записывается в виде з м с (шоб й). Выражение этого аида называется сравнением н читается тзкг г сравнимо с с по модулю й. В сравнении ни з, ни с не должны быть обязательно меньше й.
Мы больше интересуемс» остатком. Оста. ток записывается в ваде равенства з =. Дг (с1,- которое читается такг з равно остатку от деления с на й, или з равно вычету с па модулю й. Мы булеч также пользоваться скобками Дс)) дчя обозначения этнх же величии; вэтом случае й ясно из кон- текста. Еще одним обозначением является з= с (шайб), в «отсром вместо знака сравнения стоит знак равенства. Теперь это не сравнение, а остаток от лелення с на й. Вычисление остатка от сложного выражение облегчается сле- дующей теоремой, которая утверждает, что можно менять после- довательность выполнения операпни вычисленин остатна са ело.
жением н умножением. Теорема 2.6.2. Длз фиксирсгаииага модуля й (1) Д, ! -1. Ь! =. Д !Д ! )+ Д,(Ы), (11) Дг (а Ь! —. Дг !Дг (а!.Дг !ЬВ Доказатегьстго препоставляегся читателю в начестве упраж. пения. Наибольший общий делитель двух заданных положительных чисел з н !может бить вычислен с помощью итеративного применения алгоритма деления. Эта процедура известна как алгоритм Евклила. Предположим, что 1 < з; алгоритм Евклида сводится к последовательности шагов з = Дпн фгпН 1 = абаз(из + В'г, 6( Эз дипонт* л р и — л(г(1(г( ). Рз( 1( -и — Ц( Ц( - и (.
1( ( 1( — и —.. ()( -п((.(, [ зо( ] ['" ]-= Аоо ['] где остановка процесса наступаег прн получении нулевого остатка. Последний ненулевой остаток, (ы(, равен наибольшему общему делителю Этот фант будет доказан в следующей теореме Рйатрнчные обозначения позволяют кратко ззппсать шаги алгоритма Евклида в виде Теорема 2,6.3 (Алгоритм Евклида). Дяя дгук заданных лоло митсльн ы ч сгл з и 1, где з ) 1, лус(ль з(о( - з и Ро' = 1.
Решг ние рокурректных ур агний лри г —. 1,, л дается ееличикой з((= НОД Ь 1) где н раоно наименьшему целому числу, для которого 1("(.— — О. Доказательотоо Так как Р' '( < 1('( н все остатки неотрицательны, то в конце концов наступит л, для которага Р'( =. О. так что завершение рабаты алгоритма произойдет обязательно. Легко проверить, что [' -' Г'-['" '] Поэтому так что й"( должна делить оба числа з и 1 и, следовательно, лениг НОД Ь, 1). Далее, так что любой делитель чисел з н 1 делит з("( Следовательао, НОД (*, П делит гы( н делится на й"(.
Таким образом, з(т = НОД Ь, 1). Это завершает доказательство. П Из этой теоремы вытекает несколько важных следствий. Пусть А"= П[ „,] =[ „,]Ао — '(. Тогда получаем следтвит язляющшся важным и интуитивно непредсказуемы» результатом теории чисел, утверждающим. что ванбальшнй общий делитель двух пелых чисел равен нх линейной «омбннацин Следствие 2.6.4. Для любых цельш чисел э и 1 найдутся такие цеяые числа а и й, ыно НОД (г, 1) =- т Щ 66 Донаэалыльстоо. Достаточно доказать следствие для положи.
тельных з и 1. Так «ак йы =. НОД Ь, 1), то угвержденне выполняется прн а =- А,( и 6 = А,". П (> () Из доказательства этого следствия видно, кан целые числа о и 6 вычисляются в виде элементов матрппы А. Остальные два эле- мента матрнпы также имеют свою интерпретацию, для описания нагорай нам ~онадобитс» обратная к матрице А('( Напомним, что А((== П[ Отсюдз видно, что определитель матрицы А" равен ( — 1)' Обрат- ная к А" матрица равна Снедствие 2.6.6. Лолучаемые е лроцесш алгоритма Евклида матричные злементь( А((' и А((э' удоелетеоряют рооенсттм з = ( — ))" А(,"' НОД Ь, 1), 1= — ( — Н А(((НОДЬ, 1).
Докозотелт нео. Используя выписанное выше выражения для обратной матрицы н обращая первое равенства иа даказатетьства следствия 2.6 4, получаем Утверждение вытекает отсюда непосредственно. П 62 Гг 2, Пзгге абмракт тю бру зз Используя алгоритм деления, можно вычислить изибалыпий общий делитель двух целых чисел. Например, НОД 1814, 1871 находится следующим образам: [г"] Го |] [о ~~ Гз !] Га г',,Ггы], 3 — ~зч Гг~г) йд — !т тг~ ~зт) О Из этих вычислений сразу слелует, что НОД 1814, !87! равен 1! и что НОД 1814, 187! = 3'х 814 — !3 х 187 2.7.
Кольца ыногочленоп Для «аждого поля Р имеется «альца Р!к), называемое нольцом многачленов на Р. Во многих отношениях кольцо многочло нав аналогично кольцу целых чисел. Чтобы слелать зту аналогию а гв явой, в изложении данного разделаны следуем раад. 2.6. Мнвгочжна.н иад полем Р называется математическое выражение /( ) =./.х" 4-/.-н" '-" 4-/Р+/. = /г/»г, г=з где символ х называется неопределенной иергмгннай, а коэффициенты /ь ..., /„принадлежат полю. Нулевым многачгенам называется мноючлен /(х) = О. Сшгягнь многочлена обозначается дей / (х) н апределяетсл как индеис старшега ненулевого коэффициента.
По определению степень нулевою мнагачлена полагается равной отрицзтельной бесконечности ( — ) Лримдгннмм мяагачленам называется многочлен, старший коэффициент /„ которого равен 1. Два многочлена равны, если равны все их иоэфф»- цненты /,. В «ельце всех многочленов над заданным полем сложение и умножение определяются как обычные сложение и умножение мнагочленов. Такое «ольда многочленав определена для каждою поля Р н обозначаетсв символом Р (х) В исследованиях па этому кольцу элементы поля Р иногда называютсн скагярами. Суммав двух мпогочленав из Р !х1 называется другой много.
член из Р !к), определяемый равенством /(х)+ у(х) = Ш (/г+а)хг, где, конечна, члены с ивдеисом, ббльшим наибольшей нз степеней мнагочленов / (к) и й (х), равны нулю. Степень суммы не превосхолит наибольшей нз этих двух степеней. Произведением двух многочленов из Р Н ) называется многочлен из Р (х!, определяе- мый равенством / (к) у (х) .— ~ ~ к„' /,у, г)] хй Степень пронзведения равна сумме степеней множителей.
Если /(х) щ О к у (х) еь О. то / (х).у (х) чь О, так «ак дей р (х) равно отрицательной бесконечности тогда и юлька тогда, когдз р (х) .†. О. В кольце многпчленов вычааанне возможно всегда, а деление не асеева Буделг писать г (к) !з (х) к говорить, что многачлен г(х) дегшлся на мнагочлен г (к), илк что многочлен г (х) дегиш з (х), или что г (х) .пйягглюе делителем мнагочлена з (х), если сувгестнует многочлеи а (Н, такой что г (Н а (М = з (х). ненулевой мнагочлен р (х), лепящийся только иа р (Н или на провзвольный элемент а поля, называетсв нгпригадимым мнагачгелам.
Приведенный неприводвымй ннагочлен назмвается простым млагачгенам Чтобы вмяснить, является ли чнагаелен простым, надо знать поле, пал которым он рассыатривается Мноючлпн х' — 2 яв. ляется простим вад нолем рациональных чисел, на не вад полем вещественных чисел, над которым он распадается в произведение двух простых многочленов.
р (х) =- (х' — г' 2)(к' + у'2) Над полем комплексных чисел каждый из последних многачленов не является простым. Если г (х) и делит г(х), и делится иа з (х), та г (х) =- аз (х), где и — элемент поля Р. Это доказывается следующим образом. Должны существовать иногочлены а (х) и Ь (х), такие что г (х) = ...з (х) а (х) и г (х) .—. г (к) Ь (х). Следовательно, (х) — г (х) х х Ь (х) а (х). На степень стоящего справа многочлена равна суыне степеней многачленоз г (х), и (к) и Ь (к), Так как ша сумма должка рэвиятьсв степени многочлена, стоящего слева, то многочлевы о (х) н Ь (х) должны иметь степени, равные нулю, т е. являться скаляраыи Наибольший общий делитель двух мвогочленов г (х) и з (х) обозначается НОД (г (х), з (х) ! и определяется «ак приведенный чногочлеи нзнбзльшей степени, делящий одновременна оба нз них.
Если аанбадьшнй общий делитель двух мнагочленав равен 1, то они называются взаимно лросшыли. Яа меньшее общге «ршплог двух мнагочлгнов г(х) и т(х) обозначается НОК (г (к), з (х)1 и определяется как приведенный чногочлен наименьшей степени, делящийся на оба из вих Мы увидим, что наиболыпий общий делитель н наименьшее общее кратное мнагачлепав г (х) и з (х) определены однозначно. В поле вещественных чисел операция дифференцирования ввалится через операцию предельного перехода Эта определение возможно не всегда, так как в некоторых полях отсутствует во- ш Г». 2. В л т э вб тема 7 тыеет 27 К ьеа вот тш пятне арон»вольно малого числ». В таких полях удобна просто ввести операцию над ми»сочленам», результат которой ведет себя так, как вела бы производная. Такой многочле» называется формальной производной от мнагачлена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
