Евклидовость кольца многочленов над полем

Евклидовость кольца многочленов Р[х] над полем Р вытекает из следующей теоремы.

Теорема 3.13. Для любых многочленов f(x) и /Дх) Ф 0 кольца многочленов Р[х] над полем Р существуют и единственные многочлены q(x), г(х) е Р[х], такие что Дх) = /Дх) • q(x) + r(x), причем г(х) либо нулевой многочлен, либо его степень меньше степени делителя /Дх).

Доказательство. Существование. Если Дх) — нулевой многочлен или его степень меньше степени делителя /Дх), то Дх) = = /Дх) О + Дх) и, положив q(x) = 0, г(х) = Дх), получим требуемое.

Предположим теперь, что степень Дх) больше степени /Дх). Будем делить «уголком» многочлен Дх) на /Дх). Пусть Дх) = = апх” + а^х^ + ... + агх + а0, Их) = Ьтхт + Ьт_гхт-1 + ... + + Ьгх + Ь0 и п > т. Уравняем старшие члены этих многочленов,

для чего /Дх) умножим на —хп~т, а затем найдем разность

Ь,„

Получаем Дх) = /Дх) • хп_т+/Дх). Если/Дх) — нулевой многочлен или его степень меньше степени делителя, то, обо- 100

значив q(x) = — хп~т, г(х) = /Дх), получим требуемое. Если же

Ьт

степень/Дх) не меньше степени /Дх), то продолжим деление «уголком». Пусть /] (х) = Cjpck + cfc_jXfc_1 + ... + схх + с0. На втором шаге деления получаем

Таким образом, откуда

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

Если /2(х) — нулевой многочлен или его степень меньше

степени делителя /Дх), то, положив q(x) = — x,,_m +—хк~т,

bm bm

r(x) =/2(x), получим/(x) - h(x) ? q(x) + r(x), что и требовалось доказать. Если же степень/2(х) не меньше степени h(x), то продолжим деление «уголком». Поскольку степени многочленов /(x),/i(x),/2(x),... убывают, то процесс деления «уголком» конечен, и на конечном шаге мы получим требуемое равенство.

Единственность. Предположим, чтоДх) = h(x) ? q(x) + r(x) и/(х) = h(x) • qa(x) + гДх), где многочлены г(х) и га(х) либо нулевые, либо их степени меньше степени многочлена /Дх).

Тогда h(x) ? q(x) + r(x) = h(x) ? qx(x) + гДх), откуда r(x) - Г](x) = = fr(x)(qj(x) - q(x)). Если предположить, что многочлен r(x) - - гх(х) ненулевой, то его степень меньше степени многочлена /г(х), в то время как в правой части равенства стоит многочлен, степень которого не меньше степени многочлена h(x). Из полученного противоречия делаем вывод, что г(х) - г] (х) = 0, откуда г(х) = гх(х). Но тогда h(x)(q1(x) - q(x)) = 0, а так как h(x) * 0, то qx(x) - q(x) = 0 и qx(x) = q(x). Теорема доказана.

Заметим, что если в определение НОД двух многочленов включить требование, чтобы этот многочлен имел старший коэффициент, равный единице, то это обеспечит единственность НОД.

Покажем на примере, как реализуется алгоритм Евклида в Q[x].

Пример 3.3

Упростим выражение

Решение. С помощью алгоритма Евклида найдем наибольший общий делитель числителя/(х) и знаменателя g(x), а затем произведем сокращение. Чтобы избежать дробей, многочленыДх) и g(x) заменим на соответственно 3/(х) и 2g(x). Подобные преобразования в дальнейшем будем отмечать двумя чертами:

Следовательно, НОД(/Хх), g(x)) 2 - х + 1. Произведя сокращение, получим

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >