1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 67
Текст из файла (страница 67)
Алгоритм Евклида правильно находит значение НОД (а„а,). Д о к а з а т е л ь с т в о. Втот алгоритм вычисляет а~„=а;,— — а;а, для !((~й, где а,= ( а,,lа, ). Так как а„,~а, при ()1, то алгоритм, очевидно, заканчивает работу Кроме того, любой общий делитель чисел а,, н а, делит аг ы и любой общий делитель чисел а, и а, +, делит а,, Следовательно, НОД (ам а1) = =НОД(а„а,)=...
=НОД(а „а,). Очевидно, НОД(а„ьа )=а„, так что теорема доказана. П Алгоритм Евклида можно расширить так, чтобы он находил не только наибольший общий делитель чисел а, и а„но также и целые числа х и у, для которых а,х+а,у=НОД(а„а,). Сформулируем этот алгоритм. Алгоритм 8.6.
Расширенный алгоритм Евклида Вход. Положительные целые числа а, и а,. Выход. НОД(а„а,) и такие целые числа х и у, что а,х+а,у= ° =НОД(а„а,). Мепюд. Применяем программу, приведенную на рис. 8.6. О 8.8. ИОД И АЛГОРИТМ ЕВКЛИДА Ьея!п 1. х, — 1; у, - О; х, — О; у, - 1; 1 — 1; 2. И48Пе а, не делит а,, 4!о Ьея(п а--1аГ т/аГ ~; а+, — ат,— д»аГ', х,+, х,,— а»х,; У!+1 Ут-т Ч "УВ -1+ 1 епй; 8. тег!1е а,; тгг!1е х,; тег!1е у, ЕПТ( 3 4 5 б 7 Рис.
3.6. Расшнренный алгоритм Евклида. а; гч ю 67 ! О 33 О ! 24 1 — ! 9 — 1 2 6 3 — 3 3 — 4 7 Заметим, что 57х( — 4)+33х7=3. П Ясно, что алгоритм 8.6 правильно вычисляет НОД(а„а,), поскольку очевидно, что числа а, образуют требуемую последовательность остатков. В следующей лемме Описывается важное свойство чисел х; и уи вычисляемых алгоритмом 8.6. Лемма 8.4. В алгоритме 8.6 а х, +а У8 =а, при !) О. (8.23) Д о к а з а т е л ь с т в о.
Равенство (8.23) справедливо для (=О и 1= 1 в силу строки 1 алгоритма 8.6. Допустим, что (8.23) справедливо для ! — 1 и 1. Тогда хь„=х8, — дх~ в силу строки 5 и у,+,= =у,, — ду, в силу строки б. Следовательно, (8.24) а,хГ „+а,у,+, —— а,х,, + а,у,, — д (а„х, + а,у,). 337 Пример 8.9. Если а,=57 и а,=33, то для чисел а„хи и ут получаем значения Гл. в. АРиеметические опеРАции По предположению индукции и в силу (8.24) а,х,+, +а,у,+, — — а,,— чаи Так как а,,— да,=а~, в силу строки 4, то лемма доказана.
П Заметим, что лемма 8.4 даже не зависит от способа вычисления о в строке 3, хотя строка 3 существенна, чтобы гарантировать, что алгоритм 8.6 действительно вычисляет НОД(а„а,). Суммируем эти замечания в следующей теореме. Теорема 8.18. Алгоритм 8.6 вычисляет НОД(а„а1) и такие числа х и у, что а»с+а,у=НОД(а„а,). До к аз а тел ь ство.
Элементарное упражнение на применение леммы 8.4. П Определение. Пусть а, и а,— целые числа и а„а„..., ав — соответствующая последовательность остатков. Пусть дв= ( ав,/ав ~, 1(1(й. Определим (2Х2)-матрицу Ж~' "' (или Йвп если ясно, каковы а, и а,) для 0(1 ((й условиями Г1 01 1) Йи= ~0 11 для ()О 2) если 1)1, тобам — — ~1 1»~ ~»...»[ Пример 8.10. Пусть а,=57 и а,=33, последовательность остатков есть 57, 33, 24, 9, 6, 3, а частные дь 1(1~4, равны 1, 1, 2, 1.
Тогда П П Ь 1Ь 4Ь 1Ь 1~4 4П Два интересных свойства этих матриц описаны в следующей лемме. Лемма 8.5. = Яп ~ ' ~~для 1<1(й, Га, ~Ь4. У Ут ~ для 0 ( 1 ( й ху+г ул+, ~ (а) ~ г (б) )~»у= еде числа ап хи ув определяются расширенным алгоритмом Евклида. Д о к а з а т е л ь с т в о. Элементарное упражнение на применение индукции. П Введем некоторые обозначения, которые понадобятся нам в следующем разделе.
кв. ллгоэитм нлхождания нод полиномов Заметим, что все построения этого раздела годятся и для полиномов от одной переменной. Надо лишь учесть, что, в то время как наибольший общий делитель двух целых чисел определяется однозначно, для полиномов с коэффициентами из некоторого поля наибольший общий делитель единствен только с точностью до умно. жения на элемент поля. Иными словами, если Е(х) делит полиномы а,(х) и а, (х) и всякий другой их делитель тоже делит д(х), то полином сд(х), где с — отличная от нуля постоянная, также обладает этим свойством. Нас удовлетворит любой полипом, который делит а,(х) и а,(х) и делится на любой их делитель.
Чтобы обеспечить единственность, мы могли бы (но не будем) требовать, чтобы наибольший общий делитель был нормированным, т. е. чтобы коэффициент при его старшем члене был равен 1. 8.9. АСИМЛТОТИЧЕСКИ БЫСТРЫЙ АЛГОРИТМ НАХОЖДЕНИЯ НОД ЛОЛИНОМОВ При построении алгоритмов для нахождения наибольшего общего делителя мы меняем нашу схему и рассматриваем сначала случай полиномов, поскольку в случае целых чисел приходится преодолевать дополнительные трудности.
Пусть а, (х) и а, (х) — два поли- нома, наибольший общий делитель которых надо вычислить. Мы предполагаем, что СТ(а, (х))(СТ(а,(х)). Легко добиться выполнения этого условия, а именно: если СТ(а,)=СТ(а,), то заменяем полиномы а, и а, полиномами а, и а, той по т, е. вторым и третьим членами последовательности остатков, и работаем, отправляясь от них. Разобьем нашу задачу на две части. Первая состоит в построении алгоритма, отыскивающего последний член последовательности остатков, степень которого больше половины степени полинома а,. Формально, пусть ! (!) — то единственное целое число, для которого СТ(ано))1 и СТ(анп+,)е 1.
Заметим, что если а, имеет степень и, то 1(1)(п — ! — 1 в предположении, что СТ(а,)(СТ(а,), поскольку СТ(а;)(СТ(а~,) — 1 для всех 1)1. Введем рекурсивную процедуру ПНОД (полуНОД), которая по полиномам а, и а„таким, что СТ(а,))СТ(а,), формирует матрицу Р,~ (см. равд. 8.8), где 1=1(п/2), т. е. аэ — последний член последовательности остатков, степень которого больше половины степени полинома ам В основе ПНОД-алгоритма лежит тот факт„что частные от деления полиномов степеней д, и йь д,)йм зависят только от 2(Н,— — Н,)+! старших членов делимого и й,— Й,+1 старших членов делителя. Процедура ПНОД приведена на рис.
8.7. Пример 8.11, Пусть р,(х) =х'.+х'+х'+х'+х+1 Гл. а. АРиематичаскив олВРАции И р, (х) = х' — 2х'+ Зх* — х — 7. Допустим, мы пытаемся вычислить ПНОД(р„р,), Если аа=р, и а,=р„то в строках 2 и 3 т=2 и Ь, = х' -1- х' + х + 1, с, = х + 1, Ь,=х' — 2х+3, с,= — х — 7. Затем вызываем ПНОД(Ье, Ь,) в строке 4. Можно проверить, что на этом шаге )г= (1 — ( +3)~ ргоседпге ПНОД (а„а,): 1.
Д СТ(а,)<СТ(аа)у2 Феп ге1пгп ~ е!ае Ьеи(п 2. пусть па=Ьах" +с„где т= ( СТ(ае)/2 ) и СТ(с,) < «а; 3. пусть а,=Ь,х"+с„где СТ(с,)<т; сопппеп1 Ь, и Ь,— старшие члены полиномов а, и а,. Имеем СТ(Ь,) = ( СТ(аа)/2 ~ и СТ(Ь,) — СТ(Ь,) = = СТ(ае) — СТ(а,); 4. Я ПНОД (Ь„Ь,); й-'Г',1: б. 1 -д шойе; сопппеп1 е и à — соседние члены последовательности остатков, их степень не превосходит ГЗт~'2 1, т. е. а/, степени полинома аа; 7.
пусть е=уах~"'~е-1+6„где СТ(йа) < ( гл/21; 8, пусть ~=у,х~- /а-~+Й„где СТ(И,) < ( т/2~; сопипеп1 степени полиномов де и д, не превосходят т+1; 9 3 ПНОД(феэ ф1)' 10. о — (Фе ~; 11. ге1пгп 5 а ~ епй Рас. В.у. Процедура ПНОД. зев 9.9. АЛГОРИТМ НАХОЖДЕНИЯ НОД ПОЛИНОМОВ В строках б и 6 вычисляем (1 = х' — 2х'+ Зх' — х — 7, е = 4х' — 7х'+ 11х+ 22, 3 а 93 45 / = — — х' — х — —. 1б 1б 8 ' Находим, что ~ л)/2 ) =1 и, значит, в строках 7 и 8 де=4х' — 7х+11, 69=22, 3 93 45 У 8 ' 1б 1б' 1 Таким образом, в строке 9 ~1 О~ В строке 10 обнаруживаем, что (/ (х), т. е.
частное ~ с((х)/е(х) ), равно ') '/,х — '/,„. Следовательно, в строке !1 получаем результат = ~' Т -я'-ьЮ,.',,1- — ( — х — — ) — х'+ — х+ — 3( ' (,4 !6) 4 16 Г63 Заметим, что т ~р,1 ~е1 . это верно, ибо в последовательности остатков для р, и р, член е является последним полиномом, степень которого больше половины степени ро С) Рассмотрим матрицу /с, вычисляемую в строке 4 процедуры ПНОД. Предположительно, /с есть и1 )21 г() '11" ~1 где (//(х) обозначает /-е частное из последовательности остатков для Ь, и Ь„т. е. /с=/))оо~'((~1')(21).
Однако в строке б мы использовали Я как матрицу /сЬ","1(((з /м), чтобы получиты( и е, где(( — последний член последовательности остатков, степень которого больше З(п/2. Надо показать, что обе эти интерпретации матрицы /с корректны, (а,.а,) ы(ь„ь,) Т. е. /т О, (([звн21) =)с О, (п~(21). )1 Это вмчисление, конечно, можно было бы выполнить сразу после строки 5.
341 ГЛ. Е АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ Точно так же мы должны показать, что матрица 3, вычисляемая в строке 9, может играть предназначенную ей роль, т. е. Е=уе.,вп =уе/) а. (((Ф/(1) О,((Ф> ' Эти результаты вытекают из следукяцих лемм. Лемма 8.6.
Пусть /(х) =/((х) х" +~, (х), где СТ(/,)(й и д (х) =д((х) х" +д, (х), (8.26) (8.26) До к а з а те л ь с т во. Рассмотрим процесс деления /(х) на а(х) с помощью обычного алгоритма, который делит первый член полинома /(х) на первый член полинома д(х), чтобы получить первый член частного. Первый член частного умножается на а(х) и вычитается из /(х) и т. д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
