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

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

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

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

Предположим теперь, что степень Дх) больше степени /Дх). Будем делить «уголком» многочлен Дх) на /Дх). Пусть Дх) = = а_пх" + а^х^ + … + а_гх + а₀, Их) = Ь_тх^т + Ь_т__гх^т-¹ + … + + Ь_гх + Ь₀ и п > т. Уравняем старшие члены этих многочленов, для чего /Дх) умножим на —х^п~^т, а затем найдем разность.

Ь,".

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

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

степень/Дх) не меньше степени /Дх), то продолжим деление «уголком». Пусть /] (х) = Cjpc^k + c_fc_jX^fc₁ + … + с_хх + с₀. На втором шаге деления получаем.

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

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

Если /₂(х) — нулевой многочлен или его степень меньше степени делителя /Дх), то, положив q (x) = — x^,_m +—х^к~^т,

bm b_m

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

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

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

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

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

Пример 3.3

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

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

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