Краткий план. Введение в алгебру полиномов. Наибольшие общие делители полиномов над полем (стр. 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, то и .