Урок-лекция на тему: "Алгоритм Евклида"

16. Кольцо многочленов над полем. НОД двух многочленов и алгоритм Евклида. Разложение многочлена в произвольный неприводимый многочлен и его единственность.

Опр. Кольцом называется не пустое множество К = К, +, ∙  главные операции которой удовлетворяют следующим условиям:

1.               К, +,  есть абелева группа

 

        :   

       (–а) :

        

2.                 ,

Р – поле,  Р_[x] – кольцо  над полем

Опр. К – евклидово кольцо если:

1.                                                  N

2.                                                 q, r K : a = bq + r

                                              n(r) <n(b) или r=0

Р_[x] – евклидово кольцо 

Кольцо многочленов над полем является кольцом с однозначным разложением на множители, любые два элемента имеют НОД.

Опр. f g, если  g Р_[x], что а = g ∙g (r = 0)

Опр. δ Р_[x] – общий делитель f и g если f δ и gδ

Опр. d Р_[x] – НОД  f и g, если

1)                   d – общий делитель f и g

2)                   δ – общий делитель f и g  dδ

Очевидно, что многочлен делится на ненулевой многочлен ненулевой степени.

В Р_[x] обратными элементами являются элементы поля  Р̃_[x] = Р_\{0}

d = НОД (f, g) d∙ε – НОД (f, g),  ε Р_\{0}

НОД двух многочленов определяется с точностью до домножения на ненулевые элементы поля.

Опр. Два многочлена называются взаимно простыми, если НОД = 1 (=ε)

Алгоритм Евклида.

Пусть К – коммутативное кольцо.

Лемма. Пусть в коммутативном кольце К для элементов a, b, q, r выполняется равенство

(1)          a = bq + r; тогда

(2)          НОД (a, b) = НОД (b, r).

Доказательство.

Пусть d = НОД(a,b), d’ = НОД(b,r). Так как d ׀a, d ׀ b, то ввиду (1) d ׀ r. Поскольку d есть общий делитель b и r, то d ׀ d’. Аналогично убеждаемся, что  d’ ׀ d. Следовательно, d = d’

Вывод: Если к многочленам a и b кольца  Р_[x] применить алгоритм Евклида, то получающийся при этом последний ненулевой остаток есть НОД многочленов a и b.

Многочлены неприводимые над полем.

Опр. Многочлен fР_[x] называется неприводимым если он не может быть представлен в виде двух многочленов меньшей чем f степени.

Пример.

Опр. Многочлен fР_[x] называется приводимым если  и  f и g Р_[x]  f= gh

Примеры.   1) R_[x]   x²+1 неприводимый

                     2) С_[x]    x²+1=(x + i)(x – i) приводимый

Замечание: Неприводимые многочлены в Р_[x] выполняют роль простых элементов кольца.

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

 Многочлен f называется нормированным, если его старший коэффициент = 1. Любой многочлен можно представить в виде произведения элемента поля на нормированный многочлен.

Доказательство:

Существование.

1. f(x) – неприводимый

2. f(x) – приводимый f = g∙h     

Пусть g – приводим  f = g₁∙ g₂∙ h

Единственность.

Пусть

                  неприв. норм.       неприв. норм.

s = d            q_i=p_i

Доказали.

Многочлены, приводимые над полями R, С, Q