Теория исключения. Калинина Е.А - 14 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

Обобщая предшествующие рассуждения, можем выписать условие вза-
имной простоты f(x)иg(x).
Ответ. НОД (f, g) = 1 тогда и только тогда, когда R(f, g) =0,гдечисло
R(f, g) определяется формулой (1.5).
Рассмотрим теперь общую схему алгоритма Евклида. Пусть схема по-
следовательного деления имеет вид:
f(x)=g(x)q
1
(x)+r
1
(x) , 0 ≤ deg r
1
(x) < deg g(x) ,
g(x)=r
1
(x)q
2
(x)+r
2
(x) , 0 ≤ deg r
2
(x) < deg r
1
(x) ,
r
1
(x)=r
2
(x)q
3
(x)+r
3
(x) , 0 ≤ deg r
3
(x) < deg r
2
(x) ,
... ...
r
k−2
(x)=r
k−1
(x)q
k
(x)+r
k
(x) , 0 ≤ deg r
k
(x) < deg r
k−1
(x) ,
r
k−1
(x)=r
k
(x)q
k+1
(x);
т.е. r
k
(x)=НОД (f(x),g(x)). Рассмотрим первую строчку схемы. Оче-
видно, что на корнях полинома g(x) значения f(x)иr
1
(x) совпадают:
f(µ
k
)=r
1
(µ
k
). Тогда, на основании формулы (1.9), имеем
R(f, g)=(−1)
mn
b
n
0
m
k=1
f(µ
k
)=(−1)
mn
b
n
0
m
k=1
r
1
(µ
k
)=(−1)
mn
b
n−n
1
0
R(g, r
1
) ,
здесь n
1
def
=degr
1
(x). Итак, с точностью до степени старшего коэффициента
полинома g, результант полиномов f и g совпадает с результантом полино-
мов g и r
1
. Теперь перейдем ко второй строчке схемы. На основании тех
же рассуждений можем утверждать, что R(g, r
1
)=(−1)
n
1
m
b
n
1
−n
2
0
R(r
1
,r
2
),
где n
2
def
=degr
2
(x), а
b
0
— старший коэффициент полинома r
1
(x). Продол-
жаем процесс далее. На каждом шаге степени остатков понижаются, т.е.
вычисление результанта все упрощается. И если предположить, что пред-
последний остаток, т.е. r
k−1
(x), является линейным полиномом, то r
k
(x)
должен быть константой: r
k
(x) ≡ const. Согласно формуле (1.10), эта кон-
станта совпадает с R(r
k−1
,r
k
) и, следовательно, будет обращаться в нуль
тогда и только тогда, когда R(f, g) = 0. Если взять коэффициенты полино-
мов f и g символьными (буквенными) — как это было сделано в примере
1.4, то результант этих полиномов, рассматриваемый как полином относи-
тельно их коэффициентов, будет совпадать с R(r
k−1
,r
k
), с точностью до
сомножителя, являющегося рациональной функцией коэффициентов. Та-
ким образом, вычисление R(f, g) может быть произведено с помощью вы-
числения НОД (f,g) по алгоритму Евклида; именно эта схема вычисления
реализована во всех пакетах компьютерной алгебры.
Покажем теперь отношение результанта к еще одной задаче.
Задача. Найти полиномы u(x)иv(x)изA[x], обеспечивающие спра-
ведливость тождества
f(x)v(x)+g(x)u(x) ≡ НОД (f, g) , (1.13)
14

Страницы