НОД двух многочленов

Если общий делитель делится на любой другой общий делитель многочлена, то его называют этих многочленов.

Заметим, что если , то .

Пусть не делит . В таком случае найти один из многочленов можно с помощью алгоритма Евклида. Он основан на многократном применении теоремы о делении с остатком.

Так же как и в целых числах, линейно выражается через многочлены.