В алгебре наибольший общий делитель (часто сокращенно НОД) двух многочленов — это многочлен наивысшей возможной степени, который является множителем обоих исходных многочленов. Это понятие аналогично наибольшему общему делителю двух целых чисел.
В важном случае одномерных полиномов над полем полиномиальный НОД может быть вычислен, как и для целочисленного НОД, с помощью алгоритма Евклида с использованием длинного деления . Многочлен НОД определяется только с точностью до умножения на обратимую константу.
Сходство между целочисленным НОД и полиномиальным НОД позволяет распространить на одномерные многочлены все свойства, которые могут быть выведены из алгоритма Евклида и евклидова деления . Более того, НОД полинома обладает специфическими свойствами, которые делают его фундаментальным понятием в различных областях алгебры. Как правило, корни НОД двух многочленов являются общими корнями двух многочленов, и это дает информацию о корнях без их вычисления. Например, кратные корни полинома являются корнями НОД полинома и его производной, а дальнейшие вычисления НОД позволяют вычислить бесквадратную факторизациюмногочлена, который дает многочлены, корни которых являются корнями заданной кратности исходного многочлена.
Наибольший общий делитель может быть определен и существует, в более общем смысле, для многомерных многочленов над полем или кольцом целых чисел, а также над уникальной областью факторизации . Существуют алгоритмы для их вычисления, если в кольце коэффициентов есть алгоритм НОД. Эти алгоритмы используют рекурсию по количеству переменных, чтобы свести задачу к варианту алгоритма Евклида. Они являются основным инструментом в компьютерной алгебре , потому что системы компьютерной алгебры систематически используют их для упрощения дробей. И наоборот, большая часть современной теории полиномиального НОД была разработана для удовлетворения потребности в эффективности систем компьютерной алгебры.
Пусть p и q будут полиномами с коэффициентами в целочисленной области F , обычно поле или целые числа. Наибольший общий делитель p и q — это многочлен d , который делит p и q и такой, что каждый общий делитель p и q также делит d . Каждая пара многочленов (не оба равны нулю) имеет НОД тогда и только тогда , когда F является уникальной областью факторизации .
Если F — поле, а p и q не равны нулю, многочлен d является наибольшим общим делителем тогда и только тогда, когда он делит и p , и q , и он имеет наибольшую степень среди многочленов, обладающих этим свойством. Если p = q = 0 , НОД равен 0. Однако некоторые авторы считают, что в этом случае он не определен.