§3. Взаимно простые и неприводимые многочлены. Теорема и алгоритм евклида
Пусть даны два фиксированных многочлена f(x) и g(x), хотя бы один из
которых не равен нулю. Многочлен t(х) называется общим делителем f(x) и g(x), если он делит эти многочлены без остатка. Многочлен степени нуль, т.е. постоянные , всегда является общими делителями.
Определение 1. Многочлен наибольшей степени, являющийся общим делителем многочленов f(x) и g(x), называется наибольшим общим делителем (НОД) многочленов f(x) и g(x).
Если h(х) есть НОД многочленов f(x) и g(x), то НОД многочленов f(x)·х) и g(x)·х) есть h(х)·х) для любого многочлена х). Кроме этого, НОД являются соответственно и многочлены h(х) и h(х)· х), где и не равно нулю. Поэтому в дальнейшем под НОД будем понимать тот НОД, старший коэффициент которого равен 1.
Всякий общий делитель t(х) многочленов f(x) и g(x) делит НОД h(х) и всякий НОД h(х) делит f(x) и g(x); стало быть, множество общих делителей многочленов f(x) и g(x) совпадает с множеством делителей многочлена h(х).
Определение 2. Два многочлена f(x) и g(x) называются взаимно простыми, если их НОД имеет степень ноль (т.е. является не нулевой постоянной).
Если f(x) и g(x) – два взаимно простых многочлена из Рх, то существуют единственные многочлены v(x) и w(x) из Рх, обладающие тем свойством, что v(x) f(x) + w(x) g(x) = 1, причем Cm v(x) < Cm g(x), Cm w (x) < Cm f(x). Это равенство называется тождеством Безу.
Теорема Евклида. Если f(x) делит произведение g(x) c(x) и если f(x) и g(x) взаимно просты, то f(x) делит c(x).
Доказательство. В самом деле, НОД многочленов f(x) и g(x) есть ненулевая постоянная и, значит, НОД многочленов f(x) c(x) и g(x) c(x есть c(x). Но f(x) делит f(x) c(x) и, по условию, делит g(x) c(x, а, следовательно, делит их НОД, который равен c(x), и, стало быть, f(x) делит c(x).
Определение 3. Многочлен p(x) называется простым или неприводимым, если он не имеет других делителей, кроме самого себя и ненулевых постоянных.
Возьмем теперь произвольный многочлен f(x) и НОД h(x) многочленов f(x) и p(x); так как p(x) неприводим, то h(x) равен или p(x), или постоянной; в первом случае f(x) делится на p(x), а во втором f(x) взаимно прост с p(x). Таким образом, любой многочлен либо делится на p(x), либо взаимно прост с ним. Это может служить доказательством следующей теоремы для разложения многочленов на множители.
Теорема 2. Каждый многочлен f(x) из кольца P[x] степени 1, разлагается в произведение неприводимых многочленов p(x) и с точностью до порядка следования это разложение единственно
.
(3.5)
Необходимо
заметить, что понятие неприводимости
многочлена существенным образом зависит
от поля коэффициентов
так, многочлен х2
–
4
не является
неприводимым в поле Q
рациональных
чисел, поскольку он делится на х
–
2
и на х
+ 2;
многочлен х2
–
2
неприводим
в Q,
но не в R,
ибо он делится на х
+
и
на х
–
;
многочлен х2
+ 1
неприводим
в R,
а, значит, и в Q,
но не в С,
так как он делится на x
+
i
и на
x
–
i.
Заметим еще, что многочлен первой степени неприводим для любого поля Р, поскольку всякий его делитель есть либо постоянная, либо он сам и он является единственным неприводимым многочленом над полем С комплексных чисел. Над полем вещественных чисел, кроме многочлена первой степени неприводимыми будут и все многочлены второй степени, у которых дискриминант отрицателен.
Нахождение НОД: алгоритм Евклида. Пусть f(x) и g(x) – два многочлена и Cm f(x) > Cm g(x); разделим f(x) на g(x) по убывающим степеням:
f (x) = g(x)h0(х) + r0(х), Cm r0(х) < Cm g(x).
Затем разделим g(x) на r0(х),
g(x) = r0(х)h1(х) + r1(х), Cm r1(х) < Cm r0(x).
Разделим снова r0(х) на r1(х), получим остаток r2(х), степень которого меньше степени r1(х). Затем разделим r1(х) на r2(х) и т.д.; степени последовательных остатков строго убывают; следовательно, наступит момент, когда некоторый остаток rn-1(х) будет делиться на остаток rn(х), и, стало быть, получим
rn-2 (х) = rn-1 (х) hn(х) – rn(х), Cm rn (х) < Cm rn-1 (x),
rn-1(х) = rn(х) hn+1 (х).
Всякий общий делитель многочленов f(x) и g(x) делит r0(х) и, значит, он делит r1(х) и т.д., наконец, делит rn(х); обратно, всякий делитель остатка rn(х) делит rn-1(х), а значит, rn-2(х) и т.д., и, следовательно, делит f(x) и g(x); таким образом, rn(х) есть НОД многочленов f(x) и g(x).
Этот метод нахождения НОД носит название алгоритм Евклида, где слово алгоритм означает процесс вычисления.