Спільний дільник многочленів f(x) та g(x), який ділиться на кожний інший спільний дільник цих многочленів, називається їх найбільшим спільним дільником (НСД) і позначається (f,g). НСД многочленів визначається однозначно з точністю до сталого множника (оскільки, якщо d(x) – НСД , то й c·d(x),де , теж НСД).
Многочлени f(x) та g(x) називаються взаємно простими, якщо кожний їхній спільний дільник є ненульовою константою, тобто (f,g)=1.
Розглянемо спосіб знаходження НСД (алгоритм Евкліда).
Нехай дано многочлени f(x) та g(x), причому . Виконаємо послідовне ділення з остачею:
Тут оскільки послідовність степенів многочленів g(x), r1(x), r2(x),... є монотонно спадною. Оскільки степінь r1(x) не вищий за m-1, де m= deg g, то кількість кроків в алгоритмі не перевищує m.
Оскільки (f,g)=(g,r1)=(r1,r2)=(r2,r3)=…=(rn-1,rn)=(rn,0)=rn, що випливає із записаног вище алгоритму Евкліда. то остання відмінна від нуля остача rn(x) в цьому алгоритмі і є НСД многочленів f(x) і g(x).
Приклад.
З допомогою алгоритму Евкліда знайти НСД многочленів
f(x)=x3–3x2+3x–1, g(x)=x3–1.
x3–3x2+3x–1=(x3–1)·1+(-3x2+3x)
x3–1=(-3x2+3x)·()+(x–1)
-3x2+3x=(x–1)·(-3x).
Отже, (f,g)=x–1.
НСД більшої кількості многочленів, зокрема, f1(x), f2(x),…, fn(x) шукають так: