Смекни!
smekni.com

Краткий план. Введение в алгебру полиномов. Наибольшие общие делители полиномов над полем (стр. 2 из 8)

BEGIN

END

END

2. FOR i=0 TO m-n // выдача результатов

BEGIN

RETURN

RETURN

END

Очевидно что доминирует первый цикл, который выполняется m-n+1 раз. В каждом цикле происходит одно деление и пересчитывается ряд коэффициентов. Таким образом трудоёмкость алгоритма PDF есть O[n(m-n+1)]. Это как раз то время, которое нужно для вычисления произведения

над полем.

Наибольшие общие делители полиномов над полем. Дадим следующее

Определение. Пусть К – область целостности и

, причём
.

Полином

называется Наибольшим Общим Делителем (НОД) полиномов
и
если выполнены следующие условия:

1.

и

2. Если

,такой что
и
,то
и
.

Отсюда виден так называемый алгоритм Евклида для нахождения НОД двух полиномов, также использующий теорему делимости, который работает следующим образом:

, при этом

. . .

. . .

, при этом

Так как

, то очевидно что эта последовательность закончится самое большее за
шагов. При этом справедлива следующая

Теорема. Последний отличный от нуля остаток

это и есть НОД(
).

Cледует учесть что НОД может быть определён не однозначно если в области целостности имеются обратимые элементы.

Теперь пусть имеется некоторое поле F,

,
. Применяя PDF можно вычислить НОД(
).

Пусть

и
- некоторые произвольные полиномы из
. Тогда справедлива

Теорема. Если

НОД(
), то в
найдутся полиномы
и
, такие что

Доказательство: Из всех полиномов вида

выберем любой из полиномов наименьшей степени и обозначим его
. Если
не делит
, то
,
,
. Но тогда полином
имеет вид
, в противоречие с выбором
.

Из теоремы следует, что для взаимной простоты полиномов

и
необходимо и достаточно чтобы
для некоторых
.

Неприводимые сомножители полиномов. Для начала нужно сформулировать ряд известных теорем:

1. Основная теорема алгебры. Каждый полином

из
- поля комплексных чисел
имеет корень в
.

2. Отличный от константы полином

из R[x] неприводим если и только если он имеет степень 1 либо это квадратный трёхчлен с отрицательным дискриминантом.

Имеет место обратное утверждение.

Теперь для полиномов над полем K – поле.

3.Если неприводимый полином

делит произведение
то
или
.

4. Пусть

. Тогда полином
может быть однозначно представлен в произведение неприводимых нормированных полиномов над K[x]. Разложение является единственным с точностью до порядка сомножителей.

Назовём полином

примитивным, ecли его коэффициенты – целые числа, НОД которых равен 1. Тогда любой полином из
ассоциирован с некоторым примитивным полиномом (два полинома называются ассоциированными, если один из них является скалярным кратным другого). Верна теорема

5. Произведение двух примитивных полиномов из

снова примитивный полином.

Доказательство: Пусть p – простое число. По определению примитивности для простого числа p имеем:

,
, откуда

Иначе говоря никакое простое число не делит все коэффициенты многочлена

что и доказывает его примитивность.

6. (Gauss) Если

, причём
, то
, где
и
- полиномы, ассоциированные с
и
соответственно.

Полином в

неприводим если он не разлагается в произведение двух полиномов с целыми коэффициентами. В силу вышеприведённой теоремы видно, что полином неприводим в
, если и только если он неприводим как полином из
. При этом справедлива теорема

7. Если

- полином в
и
- его корень, такой что НОД(r,s)=1, то
и
.