НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ МНОГОЧЛЕНОВ. ВЗАИМНО ПРОСТЫЕ МНОГОЧЛЕНЫ.

ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ

Определение 4.1.

Многочлен j(x) из P[x] называется общим делителем многочленов g(x) и f(x) из P[x], если f(x) и g(x) делятся без остатка на j(x).

Пример 4.1. Даны два многочлена: (x) = x⁴ − 4x³ + 3x² + 2x − 6 Î R[x], g(x) = x⁴ − 3x³ − 4x² + 2х + 2 Î R[x]. Общие делители этих многочленов: j₁(x) = x³ − 4x² + 2 = Î R[x], j₂(x) = (x² − 2x − 2) Î R[x], j₃(x) = ( x − 1) Î R[x], j₄(x) = 1 Î R[x]. (Проверьте!)

Определение 4.2.

Наибольшим общим делителем отличных от нуля многочленов f(x) и g(x) из P[x] называется такой многочлен d(x) из P[x], который является их общим делителем и сам делится на любой другой общий делитель этих многочленов.

Пример 4.2. Для многочленов из примера 4.1. f(x) = x⁴ − 4x³ + 3x² + 2x − 6 Î R[x], g(x) = x⁴ − 3x³ − 4x² + 2х + 2 Î R[x] наибольшим общим делителем будет многочлен d(x) = j₁(x) = x³ − 4x² + 2 Î R[x], т. к. этот о многочлен d(x) делится на все другие их общие делители j₂(x), j₃(x), j₄(x) .

Наибольший общий делитель (НОД) обозначается символом:

d(x) = (f(x), g(x)).

Наибольший общий делитель существует для любых двух многочленов f(x),g(x) Î P[x] (g(x) ¹ 0). Его существование определяет алгоритм Евклида, который заключается в следующем.

Делим f(x) на g(x). Остаток и частное, полученные при делении, обозначим r₁(x) и q₁(x). Затем, если r₁(x) ¹ 0, делим g(x) на r₁(x), получаем остаток r₂(x) и частное q₂(x) и т.д. Степени получающихся остатков r₁(x), r₂(x), … будут убывать. Но последовательность целых неотрицательных чисел ограничена снизу числом 0. Следовательно, процесс деления будет конечным, и мы придем к остатку r_k(x), на который нацело разделится предыдущий остаток r_{k – 1}(x). Весь процесс деления можно записать следующим образом:

f(x) = g(x) × q₁(x) + r₁(x), deg r₁(x) < deg g(x);

g(x) = r₁(x) × q₂(x) + r₂(x), deg r₂(x) < deg r₁(x);

. . . . . . . . . . . . . . . . . . . . . . . .

r_{k – 2} (x) = r_{k – 1} (x) × q_k (x) + r_k (x), deg r_k (x) < deg r_{k – 1} (x);

r_{k – 1} (x) = r_k (x) × q_k+1 (x). (*)

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

1) Покажем, что r_k (x) является общим делителем данных многочленов.

Обратимся к предпоследнему равенству:

r_{k –-2} (x) = r_{k –-1} (x) × q_k (x) + r_k (x), или r_{k –-2} (x) = r_k (x) × q_k+1 (x) × q_k (x) + r_k (x).

Его правая часть делится на 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 –- 1} (x) и r_{k –- 2} (x) делятся на r_k (x), отсюда следует, что и сумма в правой части равенства делится на r_k (x). Значит и левая часть равенства делится на r_k (x), т.е. r_{k –- 3} (x) делится на r_k (x). Продвигаясь таким образом последовательно вверх, мы получим, что многочлены f(x) и g(x) делятся на r_k (x). Тем самым мы показали, что r_k (x) является общим делителем данных многочленов (определение 4.1.).

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

Обратимся к первому равенству: f(x) = g(x) × q₁(x) + r₁ (x).

Пусть d(x) – некоторый общий делитель f(x) и g(x). Тогда по свойствам делимости разность f(x) – g(x) × q₁(x) также делится на d (x), то есть левая часть равенства f(x) – g(x) × q₁(x) = r₁ (x) делится на d (x). Тогда и r₁ (x) будет делиться на d (x). Продолжая рассуждения аналогичным образом, последовательно опускаясь по равенствам вниз, получим, что r_k (x) делится на d (x). Тогда, согласно определению 4.2.r_k (x) будет являться наибольшим общим делителем многочленов f(x) и g(x): d(x) = (f(x), g(x)) = r_k (x).

Наибольший общий делитель многочленов f(x) и g(x) является единственным с точностью до множителя - многочлена нулевой степени, или, можно сказать, с точностью до ассоциированности (определение 2.2.).

Таким образом, нами доказана теорема:

Теорема 4.1. /Алгоритм Эвклида/.

Если для многочленов f(x),g(x) Î P[x] (g(x) ¹ 0) верна система равенств и неравенств (*),то последний, не равный нулю остаток будет наибольшим общим делителем этих многочленов.

Пример 4.3. Найти наибольший общий делитель многочленов

f(x) = x⁴ + x³ +2x² + x + 1 и g(x) = x³ –2x² + x –2.

Решение.

1шаг.2шаг.

Запишем шаги деления в виде системы равенств и неравенств, как в (*) :

f(x) = g(x) × q₁(x) + r₁(x), deg r₁(x) < deg g(x);

g(x) = r₁(x) × q₂(x).

Согласно Теореме 4.1./Алгоритм Эвклида/ последний, не равный нулю остаток r₁(x) = 7x² + 7 будет наибольшим общим делителем d(x) этих многочленов:

(f(x), g(x)) = 7x² + 7.

Поскольку делимость в кольце многочленов определена с точностью до ассоциированности (Свойство 2.11.) , то в качестве НОД можно взять не 7x² + 7, а (7x² + 7) = x² + 1.

Ответ: будем считать, что (f(x), g(x)) = x² + 1.

Определение 4.3.

Наибольший общий делитель со старшим коэффициентом 1 будем называть нормированным наибольшим общим делителем.

Пример 4.4. В примере 4.2. был найден наибольший общий делитель d(x) = (f(x), g(x)) = 7x² + 7 многочленов f(x) = x⁴ + x³ +2x² + x + 1 и g(x) = x³ –2x² + x –2. Заменив его на ассоциированный с ним многочлен d¹(x) = x² + 1, получим нормированный наибольший общий делитель этих многочленов(f(x), g(x)) = x² + 1.

Замечание.Применяя алгоритм Евклида при поиске наибольшего общего делителя двух многочленов, можно сделать следующее заключение. Наибольший общий делитель многочленов f(x) и g(x) не зависит от того, будем ли мы рассматривать f(x) и g(x) над полем P или над его расширением P’.

Определение 4.4.

Наибольшим общим делителем многочленов f₁(x), f₂(x), f₃(x),… f_n(x) Î P[x] называется такой многочлен d(x) Î P[x], который является их общим делителем и сам делится на любой другой общий делитель этих многочленов.

Поскольку алгоритм Евклида пригоден лишь для поиска наибольшего общего делителя двух многочленов, то для поиска наибольшего общего делителя n многочленов требуется доказать следующую теорему:

Теорема 4.2.

(f₁(x), f₂(x), f₃(x),… f_n(x)) = ((f₁(x), f₂(x), f₃(x),… f_n-1(x)), f_n(x)).

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

o Введем обозначения: (f₁(x), f₂(x), f₃(x),… f_n-1(x)) = d₁(x), (d₁(x), f_n(x)) = d(x), и докажем, что d(x) = (f₁(x), f₂(x), f₃(x),… f_n(x)).

СогласноОпределению 4.4.нужно доказать два условия для d(x):

1) f₁(x), f₂(x), f₃(x),… f_n(x) d(x);

2) d(x) d(х), где d(х) – любой другой делитель f₁(x), f₂(x), f₃(x),… f_n(x).

Докажем, что первое условие выполняется.

Т.к. d(x) = (d₁(x), f_n(x)), то f_n(x) d(x) и d₁(x) d(x).

Но т.к f₁(x), f₂(x), f₃(x),… f_n-1(x) d₁(x), а d₁(x) d(x), то f₁(x), f₂(x), f₃(x),… f_n-1(x) d(x) (Свойство 2.7.)Þ f₁(x), f₂(x), f₃(x),… f_n-1(x), f_n(x) d(x).

Докажем, что второе условие выполняется.

Пусть d(х) – любой другой делитель f₁(x), f₂(x), f₃(x),… f_n-1(x), f_n(x).

Тогда d(х) – любой другой делитель f₁(x), f₂(x), f₃(x),… f_n-1(x), а d₁(x) = (f₁(x), f₂(x), f₃(x),… f_n-1(x)) Þ d₁(x) d(х) (Определение 4.4.).

Тогда d(х) –делитель f_n(x) и d₁(x).

Но d(x) = (d₁(x), f_n(x))Þ d(x) d(х) (Определение 4.4.). ·

Не нашли, что искали? Воспользуйтесь поиском по сайту: