Пусть - последний отличный от нуля остаток

Можно показать, что

= НОДº(,).

Действительно, просмотр равенств (1) снизу вверх показывает, что является делителем , т.е. общим делителем и .

Просмотр равенств (1) сверху вниз показывает, что все остатки делятся на любой общий делитель и .

Докажем вторую часть теоремы.

Предположим, что существуют два НОД

= НОДº(,),

= НОДº(,).

Тогда, согласно определению НОДº(,),

и, с учетом правила

=+,

имеем

и многочлены и отличаются лишь множителем нулевой степени и, следовательно, наше предположение неверно.

Пример. Пусть заданы два многочлена :

Требуется найти НОДº(,). Алгоритм поиска НОДº(,):