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

8. (критерий Эйзенштейна) Пусть

- полином в . Если существует такое простое число p, что p не делит и делит остальные коэффициенты , но не делит , тогда полином неприводим.

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

Разложение полиномов на свободные от квадратов множители. Полином

называется свободным от квадратов, если не найдётся полинома положительной степени, такого что . Cправедлива

Теорема. Пусть K - область с однозначным разложением на множители, характеристики нуль. И пусть

- примитивный полином в K[x], отличный от константы. Возьмём его однозначное разложение на множители . Его производную обозначим . Тогда НОД( , )=

Доказательство: Обозначим

и r(x)= НОД( , ). Тогда и , откуда следует что . Методом от противного можно показать что не делит r(x). Предположим что . Тогда , откуда можно заключить что . Отсюда после сокращений . Cтало быть потому что НОД( )=1. Из этого можно заключить что . Очевидное противоречие.

Из теоремы легко выводятся два следствия.

Следствие1. Простые корни полинома не являются корнями его производной.

Cледствие2. Пусть K – поле,

- неприводимый полином в K[x], который делит . Тогда если и только если .

Пусть

- примитивный полином, определённый на области с однозначным разложением на множители K, . Пусть . Для положим , . Тогда называется разложением полинома на свободные от квадратов множители.

Замечание. Некоторые из полиномов

могут быть единицей, - произведение всех линейных множителей, cоответствующим простым корням, - произведение всех линейных множителей, cоответствующим двойным корням и т.д.

Так как r(x)= НОД(

, )= (здесь без ).

Наибольший свободный от квадратов делитель полинома

равен .

Cледовательно,

НОД(

, )= .

Поэтому

. Повторяя процесс с вместо мы можем вычислить как первый свободный от квадратов сомножитель , и в конце можно получить все свободные от квадратов сомножители . Таким образом получен алгоритм, известный под названием PSQFF(Polynomial Square Free Factorization).

Вход:

- примитивный полином, определённый на области с однозначным разложением на множители K, , char(K)=0.

Выход: полиномы

и вышеопределённое число e, определяющие разложение на свободные от квадратов множители.

На условном языке программирования алгоритм выглядит примерно так:

BEGIN // первоначальная инициализация

j:=1

label:

IF

THEN // выход?

BEGIN

e:=j

EXIT

END

v(x):=

// вычисляем

// обновляем

INCR(j)

GOTO label

END

Основные факты о конечных полях. Из определения поля видно, что каждое поле – область целостности, обратное утверждение в общем случае неверно. Но имеет место следующее утверждение:

Каждая конечная область целостности – поле.

Если взять два неравных элемента a,b из конечной области целостности K , то для всех ненулевых элементов

по правилу сокращения . Поэтому сК=К и найдется такой , что , что и означает наличие у каждого ненулевого элемента конечной области целостности мультипликативного обратного элемента, что и подтверждает что K- поле.

Так как ненулевые элементы любого конечного поля из q элементов образуют абелеву группу порядка q-1 относительно умножения, то справедлива