§2. Деление многочленов с остатком. Алгоритм Евклида. Критерий взаимной простоты двух многочленов.

Многочлен – это а₀+а₁х¹+….+ а_nхⁿ, где а₀,а_1,…,а_n –элементы поля P. Кольцо всех многочленов с коэффициентами из поля Р от известного х обозначим через Р[х].

Рассмотрим алгоритм деления с остатком.

Т1 (о существовании частного и остатком).

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

Замечание. Степень r(х) это deg r(x).

Т2 (о единственности частного остатка). Независимо от процесса их получения частное и остаток при делении многочлена f(x) из Р[х] на многочлен g(x) из Р[х] определяются единственным образом.

Д-во. Методом от противного.

Предположим, что кроме q(x) и r(х), существуют частное q₁(x) и остаток r₁(x). Тогда:

1). f(x)=g(x)q(x)+r(x) 2). f(x)=g(x) q₁(x)+ r₁(x).

Вычтем из 1) 2), получим:

0=g(x)[q(x)-q₁(x)]+[r(x)-r₁(x)]

или g(x)[q(x)-q₁(x)]=r₁(x)-r(x)

Если q(x)- q₁(x) , deg[ g(x) [q(x)- q₁(x)]]>= m

Тогда deg(r₁(x)-r(x)) >= m, что невозможно,т.к. deg r(x) < m и deg r₁(x)< m

Значит, q₁(x) -q(x)=0 и r₁ (x)- r(x)

Следовательно, q(x)= q₁(x), r(x)= r₁(x)

О1. Пусть f(x) и g(x) - два многочлена из Р[х]. Третий многочлен d(x) из того же кольца Р[х] наз. общим делителем f(x) и g(x), если d(x) делит как f(x), так и g(x).

О2. Наибольшим общим делителем двух многочленов f(x) и g(x) из Р[х] называется третий многочлбн D(x) из того же кольца Р[х], удовлетворяющий двум условиям:

1. D(x) является общим делителем f(x) и g(x)

2. D(x) делится на любой другой их общий делитель

Теорема З.(алгоритм Евклида) НОД существует для любых многочленов f(x) и g(x) из Р[х].

Способ нахождения HOD, называемый алгоритмом Евклида: Делим f(x) на g(x); остаток и частные, полученные при делении, обозначим соответственно через q(x) и r(х). Причем deg r(x)<deg g(x). Затем делим g(x) на r(х), получим остаток r₁(x) и частное q₁(x). Причем deg r₁(x)<deg r(x). Затем делим r₁ (x) на r₂(х) и т.д.

Степени получающихся при таком процессе остатков r(x), r_l(х),r₂(х)… будут, все время убывать. Но целые неотрицательные числа не могут убывать безгранично. Следовательно, процесс деления не может быть бесконечным - придем к остатку r_k+1= 0.

Покажем, что последний, отличный от нуля остаток r_k(х) и будет НОД многочленов f(x) и g(x).

Запишем весь процесс деления следующим образом:

f(x)=g(x)q(x)+r(x)

g(x)=r(x) q₁(x)+r₁(x)

r(x) = r₁(x) q₂(x)+ r₂(x)

r₁(x) =r₂(x) q₃(x)+ r₃(x) (3)

r_k-2(x)= r_k-1 (x) q_k(x)+ r_k(x)

r_k-1 (x) = r_k(x) q_k+1(x)

Рассмотрим r_k-1(x)=r_k(x)q_k+1(x)r_k(x):r_k(x) (по свойству делимости). Значит r_k-1 (x): r_k(x). Рассмотрим r_k-2(x)= r_k-1 (x) q_k(x)+ r_k(x) , r_k-1 (x): r_k(x) (no доказанному) r_k(x):r_k(x) Следовательно, по свойству делимости, левая часть r_k-2(x) делится на r_k(x).

Рассмотрим r_k-3(x)= r_k-2 (x) q_k-1(x)+ r_k-1(x)

Здесь r_k-2 (x) : r_k(x)по доказанному, r_k-1(x): r_k(x)

Следовательно, по свойству делимости, левая часть r_k-3(x) делится на r_k(x).

Двигаясь, таким образом, постепенно вверх, дойдем до многочленов f(x) и g(x) и убедимся, что f(x) и g(x) делятся на r_k(x).

Докажем, что r_k(x) делится на любой другой общий делитель многочленов f(x) и g(x).

Пусть d(x) - некоторый общий делитель f(x) и g(x). Надо доказать, что r_k(x): d(x).

Из равенств (3) получаем равенства (4).:

(3)

Рассмотрим r(x) = f(x)- g(x) q(x) Так как f(x): d(x) и g(x): d(x), то разность f(x)- g(x) q(x)= r(x) должна делится на d(x). Рассматривая второе равенство системы (4): r₁(x) =g(x)-r(x)q₁(x) , находим, что g(x): d(x) (по условию) и r(х): d(x) (по доказанному), значит, r₁(x): d(x) и т.д.. Так, опускаясь постепенно вниз, мы дойдем до r_k(х) и убедимся, что r_k(х) :d(x). Значит, r_k(х) есть нод многочленов f(x) и g(x).

Т4. НОД многочленов f(x) и g(x) является единственным с точностью до множителя нулевой степени.

Д-во. Пусть D₁(x) и D₂(x) - два НОД многочленов f(x) и g(x). По определению HOD D₁(x): D₂(x) и D₂(x): D₁(x), откуда по свойству делимости D₁(x) и

D₂(x) отличаются числовым множителем.

Следствие. Если D(x) - наибольший общий делитель f(x) и g(x) из Р[х], то в том же самом кольце Р[х] можно подобрать такую пару многочленов и , что

О. Два многочлена f(x) и g(x) наз. взаимно простыми, если их нод - многочлен нулевой степени.

Т5. (критерий взаимной простоты двух многочленов). Многочлены f(x) и g(x) из Р[х] являются взаимно простыми тогда и только тогда, когда в том же кольце Р[х] можно подобрать такую пару многочленов и , что справедливо равенство: (*)

Д-во. Если (f(x), g(x))=l, то существование многочленов и , удовлетворяющих равенству (*), следует из следствия из алгоритма Евклида.

Обратно, пусть многочлены и , удовлетворяющие равенству (*), существуют. Тогда, если допустить, что (f(x), g(x))= d(x), то из равенства (*) будет следовать, что 1: d(x), что может выполняться лишь про d(x)=l. Следовательно,(f(x), g(x))=l