Пусть даны два фиксированных многочлена f(x) и g(x), хотя бы один из

которых не равен нулю. Многочлен t(х) называется общим делителем f(x) и g(x), если он делит эти многочлены без остатка. Многочлен степени нуль, т.е. постоянные _  , всегда является общими делителями.

Определение 1. Многочлен наибольшей степени, являющийся общим делителем многочленов f(x) и g(x), называется наибольшим общим делителем (НОД) многочленов f(x) и g(x).

Всякий общий делитель t(х) многочленов f(x) и g(x) делит НОД h(х) и всякий НОД h(х) делит f(x) и g(x); стало быть, множество общих делителей многочленов f(x) и g(x) совпадает с множеством делителей многочлена h(х).

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

Определение 3. Многочлен p(x) называется простым или неприводимым, если он не имеет других делителей, кроме самого себя и ненулевых постоянных.

Возьмем теперь произвольный многочлен f(x) и НОД h(x) многочленов f(x) и p(x); так как p(x) неприводим, то h(x) равен или p(x), или постоянной; в первом случае f(x) делится на p(x), а во втором f(x) взаимно прост с p(x). Таким образом, любой многочлен либо делится на p(x), либо взаимно прост с ним. Это может служить доказательством следующей теоремы для разложения многочленов на множители.

Теорема 2. Каждый многочлен f(x) из кольца P[x] степени 1, разлагается в произведение неприводимых многочленов p(x) и с точностью до порядка следования это разложение единственно

. (3.5)

Необходимо заметить, что понятие неприводимости многочлена существенным образом зависит от поля коэффициентов   так, многочлен х 2 – 4 не является неприводимым в поле Q рациональных чисел, поскольку он делится на х – 2 и на х + 2; многочлен х 2 – 2 неприводим в Q, но не в R, ибо он делится на х +и на х –; многочлен х 2 + 1 неприводим в R, а, значит, и в Q, но не в С, так как он делится на x + i и на x – i.

Заметим еще, что многочлен первой степени неприводим для любого поля Р, поскольку всякий его делитель есть либо постоянная, либо он сам и он является единственным неприводимым многочленом над полем С комплексных чисел. Над полем вещественных чисел, кроме многочлена первой степени неприводимыми будут и все многочлены второй степени, у которых дискриминант отрицателен.

Разделим снова r₀(х) на r₁(х), получим остаток r₂(х), степень которого меньше степени r₁(х). Затем разделим r₁(х) на r₂(х) и т.д.; степени последовательных остатков строго убывают; следовательно, наступит момент, когда некоторый остаток r_n-1(х) будет делиться на остаток r_n(х), и, стало быть, получим

Этот метод нахождения НОД носит название алгоритм Евклида, где слово алгоритм означает процесс вычисления.