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

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

Пример 4.2. Для многочленов из примера 4.1. f(x) = x 4 − 4x 3 + 3x 2 + 2x − 6 Î R[x], g(x) = x 4 − 3x 3 − 4x 2 + 2х + 2 Î R[x] наибольшим общим делителем будет многочлен d(x) = j₁(x) = x 3 − 4x 2 + 2 Î R[x], т. к. этот о многочлен d(x) делится на все другие их общие делители j₂(x), j₃(x), j₄(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). Весь процесс деления можно записать следующим образом:

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

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

Его правая часть делится на r_k (x). Следовательно, левая часть также делится на r_k (x), т.е. r_{k –-2} (x) делится на r_k (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), то есть является наибольшим общим делителем этих многочленов.

Пусть 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.).

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

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