Теорема. Наибольший общий делитель

Теорема

$r_s$ из алгоритма Евклида является наибольшим общим делителем многочленов $f(x)$ и $g(x)$

Доказательство

Необходимо доказать два факта: $r_s$ это общий делитель $f$ и $g$ и он имеет наибольшую степень.

Из последнего равенства следует, что $r_{s-1}{r}_s$
Из предпоследнего получаем, что $r_{s-2}=r_s\cdot q_{s+1}\cdot q_s+r_s=r_s\left(q_{s+1}{q}_s+1\right)$, т. е. $r_{s-2}⋮r_s$
Далее, поднимаясь вверх до второго и первого равенств, получим, что $f,g⋮r_s$
Теперь предположим, что существует многочлен $h(x)$ большей степени, являющийся общим делителем $f$ и $g$

Тогда благодаря первому равенству $r⋮h$, благодаря второму $r_1⋮h$; и так далее вплоть до предпоследнего равенства, из которого получим, что $r_s⋮h$, что невозможно. Следовательно, такого многочлена не существует и $r_s$ является НОД( $f,g$ )

многочлены