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

UptoLike

ВУЗ: 

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

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

Рубрика: 

1.2 Результант и алгоритм Евклида
Итак, согласно теореме 1.1, условие R(f, g) = 0 равносильно существова-
нию общего корня полиномов f(x)иg(x), или же, иными словами, нетриви-
ального наибольшего общего делителя НОД (f, g) этих полиномов. Обратно,
условие R(f, g) = 0 гарантирует взаимную простоту полиномов f(x)иg(x),
т.е. то, что НОД (f, g)=const = 0. Поскольку конструктивное вычисление
НОД (f, g) может быть организовано по алгоритму Евклида, следует ожи-
дать, что в этом алгоритме выражение для R(f, g)должноявнопроявиться
на каком-то этапе.
Пример 1.4. Найти условия взаимной простоты полиномов
f(x)=a
0
x
2
+ a
1
x + a
2
и g(x)=b
0
x
2
+ b
1
x + b
2
,a
0
=0,b
0
=0 .
Решение. Первым шагом алгоритма Евклида будет деление (с остат-
ком) f(x)наg(x):
f(x)=
a
0
b
0
g(x)+
a
1
−
a
0
b
1
b
0
x +
a
2
−
a
0
b
2
b
0

def
= r
1
(x)
.
Предположим сначала, что a
1
b
0
− a
0
b
1
= 0. Тогда второй шаг алгоритма
Евклида заключается в делении g(x)наr
1
(x). После длинных выкладок
получим:
g(x)=r
1
(x)
b
0
a
1
b
0
− a
0
b
1
b
0
x +
b
1
− b
0
a
2
b
0
− a
0
b
2
a
1
b
0
− a
0
b
1

+
b
0
R(f, g)
(a
1
b
0
− a
0
b
1
)
2

def
= r
2
(x)
,
где R(f, g) в точности совпадает с результантом (1.5).
Теперь проанализируем НОД (f, g) в зависимости от величины R(f, g).
Если R(f, g) = 0, то очевидно, что на следующем, т.е. третьем, шаге ал-
горитм Евклида остановится и НОД (f, g)=r
2
(x)=const =0. Вэтом
случае полиномы f(x)иg(x) взаимно просты. Если же R(f,g)=0,то
НОД (f, g)=r
1
(x), т.е. НОД является линейным по x полиномом.
Предположим теперь, что a
1
b
0
− a
0
b
1
= 0. Алгоритм Евклида остано-
вится уже на втором шаге. Полиномы f(x)иg(x)будутвзаимнопростыми
при a
2
b
0
− a
0
b
2
= 0. Одновременное выполнение условий
a
1
b
0
− a
0
b
1
=0 и a
2
b
0
− a
0
b
2
=0
равносильно тому, что коэффициенты полиномов f(x)иg(x)пропорцио-
нальны, т.е. f(x)=Cg(x) при некоторой константе C.ТогдаНОД (f, g)
совпадает с любым из этих полиномов.
13

Страницы