§3. Деление с остатком в кольце p[X].

Определение 1. Многочлен f(x)  P[x] делится на многочлен g(x)  0 из этого же кольца с остатком, если h(x) и r(х) из Р[х]: f(x)= g(x) h(x)+r(x), где cm r(x) <cm g(x)  r(x) = 0.

Теорема 1. Для любой пары многочленов f(x) и g(x) из кольца Р[х], где g(x)  0, ! пара многочленов h(x) и r(х) из

Р[х]: f(x)=g(x) h(x)+r(x), причём cm r(x) < cm g(x)  r(x)=0

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

Докажем существование такой пары многочленов.

Пусть f(x) = a_nxⁿ+a_n-1 x^n-1+...+ а₁x+ а₀

g(x) = b_sх^s+b_s-1 х^s-1+…+b₁x+b₀

При этом возможны два случая:

1-й случай: f(x) = 0 или cm f(x) < cm g(x), тогда

f(x) = g(x) • 0 + f(x) и искомые многочлены будут равны:

h(x) = 0, r(x) = f(x)

2-й случай: cm f(x)  cm g(x), и пусть cm f(x) = n, т.е. а_n  0,

cm g(x)=s, т.е. b_s  0

Тогда, вычтем из многочлена f(x) многочлен Получим:(1)

cm f₁(x) < cm f(x), т.к. в процессе вычитания член a_nxⁿ будет уничтожен.

Если cm f₁(x) > cm g(x), то опять повторим процедуру понижения степени

(2) , гдеcm f₂(x) < cm f₁(x)

Если cm f₂(x)  cm g (x), то опять повторим процедуру понижения степени до тех пор пока не получим многочлен f_k(x), степень которого будет меньше ст. g(x), т.е. равенство:

Складывая почленно равенства (1),(2).... ,(k), получим:

Обозначим f_k(x)= r(x), т.к. его степень меньше cm g(x), тогда f(x)=g(x)h(x) + r(x) (**)

Докажем единственность такого представления:

Предположим противное, пусть

f(x)=g(x) h(x)+r(x),

где

cm r(х) < cm g(x)  r(x) = 0

и

f(x) = g(x)h₁(x)+r₁(x),

где

cm r₁(х) < cm g(x)  r₁(x)=0

Тогда, g(x) [h(x) – h₁(x)]= r₁(x) - r (x), cm g(x) + cm [h(x) – h₁(x)] = =cm (r₁(x) - r(х)), т.е. cm g(x)  cm (r₁(x) - r(x)), что противоречит определению отношения делимости многочленов с остатком. Следовательно, (h₁(x) = h₂(х)) & (r₁(x) = r(x)). Таким образом, отношение делимости в кольце Р[х] обладает почти теми же свойствами, что и в кольце Z, однако есть и небольшие различия, например, кольцо Р[х] более богато обратимыми элементами, чем кольцо Z.

Так, относительно операции умножения в кольце Z всего два обратимых элемента 1, -1, а в кольце Р[х] это все многочлены нулевой степени, т.е. элементы поля Р.

Понятия HОД(f, g) и HOK(f, g) определяются с точностью до постоянного множителя (с), а в кольце Z с точностью до знака.

Действительно, если даны два многочлена f(x) и g(x), а d₁(x) и d₂(x) их НОД, то (d₁(x) /d₂(x)) & (d₂(x) /d₁(x)) => d₁(x) = cd₂(x) (см. св - во 3), т.е. НОК и НОД определяются с точностью до множителя из поля Р. Так же как и в кольце Z на основе доказанной выше теоремы можно записать алгоритм Евклида: для f(x), g(x)P[x], g(x)  0 и доказать, что последний остаток r_n(х)  0 в этом алгоритме будет НОД(f(x), g(x)), что одновременно доказывает и существование НОД(f, g) для  f, g  P[x].

Задача 1. В кольце Z₅[х] найти НОД(f, g) и HOK[f, g], если

f(x) = x² + x + ,g(x) = x³ –

Решение. Для нахождения НОД(f, g) используем алгоритм Евклида. Делим "углом"' g(x) на f(х)

Итак HOД(f, g) =

Для нахождения HOK[f, g] воспользуемся формулой

итак, HOK[f, g] =

Замечание. В процессе выполнения алгоритма Евклида не только сами многочлены f(x) и g(x), но и получаемые остатки можно умножать на любые числа (не равные нулю), чтобы в частном получались только целые коэффициенты. При этом, конечно, частное искажается, остаток от деления остается с точностью до ассоциированности.

Однако, этого делать нельзя, когда решаем

Задачу 2. В кольце Q[x] с помощью алгоритма Евклида найти линейное представление НОД(f, g), если

f(x) = x⁵ - 5x⁴ - 2х³ + 12х - 2х + 12

g(x)= х³ – 5x² – 3x + 17

Решение.

Найти линейное представление - это значит найти многочлены u(х) и v(x): d(x) = f(x)u(x) + g(x)v(x). Делим f(х) на g(x):

0=r₃(x)

Итак, HOД(f, g)=2

Теперь запишем процесс деления многочленов в виде равенств:

f(x) = g(x)•(x² + l) + (x - 5), g(x) = (x - 5)•(x² - 3) + 2

Выразим из последнего равенства (f,g) = 2 2 = g(x) - (x - 5)•(x² - 3) (*)

Из первого равенства выразим остаток r(х) = (х - 5), х - 5 = f(x) - g(x)(x²- 1) и подставим в равенство (*).

Получим:

2 = g(x) - [f (x) - g(x)(x² + 1)](х² - 3)

2 = g(x) - f(х)(х² + 3) + g(x)(x² + 1)(х² - 3)

2 = g(x)[l + (х² + 1)(х² - 3)] + f (х)(3 - х²)

v(x) = l + (x²+l)(x² -3) = 1+х⁴ - 3х² + х² - 3=х⁴ - 2х² - 2

Ответ: u(x)=3 - x², v(x)=x⁴ – 2x² -2

Замечание. В этой задаче использовались неполные частные, поэтому нельзя домножать многочлены на множители из поля Q.

Определение 2. Многочлены f(x) и g(x) называются взаимно простыми, если (f, g)=c, где с  Р.

Чтобы снять неоднозначность, вводится понятие нормированного многочлена.

Определение 3. Многочлен f(x)  P[x] называется нормированным, если коэффициент при его старшем члене равен 1.

Например, f(x)=x⁵ + 3x⁴ - 2x² + 2. Тогда, если f(x) и g(x) нормированные и взаимно простые, то (f, g)=l.

Имеет место следующая теорема:

Критерий взаимной простоты: (f, g) = l   u, v  P[x]:

f(x)u(x) + g(x)v(x) = 1.

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

Необходимость. Так как многочлены f и g взаимно просты, то всегда можно записать: fu + gv = l (смотри алгоритм Евклида).

Докажем достаточность. Пусть fu + gv = l, докажем, что (f, g) = l. Предположим противное, пусть многочлены f(x) и g(x) не являются взаимно простыми, т.е. (f, g) = d  l. Тогда (f/d) & (g/d) => (fu+gv)/d => (l/d) => cm d(x) = 0 => (d = l).