Наибольший общий делитель полиномов
Пусть даны два различных наибольших общих делителя $d_{0} (x)$ и $d_{1} (x)$ полиномов $f_{0} (x)$ и $f_{1} (x)$.
По определению НОД $d_{0} (x) = h_{1} (x)d_{1} (x)$, а $d_{1} (x)=h_{0} (x)d_{0} (x)$. Следовательно, $d_{0} (x)=h_{1} (x)h_{0} (x)d_{0} (x)$, поэтому $\deg [h_{0} (x)h_{1} (x)]=0$, отсюда $\deg h_{0} (x)=\deg h_{1} (x)=0$, т. е. полиномы $h_{0} (x)$ и $h_{1} (x)$ являются константами.
Алгоритм Евклида
Приведем конструктивный способ построения НОД двух полиномов $f_{0} (x)$ и $f_{1} (x)$, который называется алгоритмом Евклида.
Пусть для определенности $\deg f_{0} (x)\ge \deg f_{1} (x)$. Делим полином $f_{0} (x)$ на полином $f_{1} (x)$ с остатком, получаем $f_{0} (x)=f_{1} (x)q_{1} (x)+r_{1} (x)$. Теперь полином $f_{1} (x)$ делим на остаток от деления $r_{1} (x)$, имеем $f_{1} (x)=r_{1} (x)q_{2} (x)+r_{2} (x)$. Затем полином $r_{1} (x)$ делим на $r_{2} (x)$ и т. д. В итоге получаем цепочку равенств: \begin{align} f_{0} &= f_{1} q_{1} +r_{1},\\ f_{1} &= r_{1} q_{2} +r_{2},\\ r_{1} &= r_{2} q_{3} +r_{3},\\ &...,\\ r_{k-2} &= r_{k-1} q_{k} +r_{k},\\ r_{k-1} &= r_{k} q_{k+1}. \end{align} Так как $\deg r_{1} >\deg r_{2} >\cdots >\deg r_{k-1} >\deg r_{k} $, то цепочка равенств конечна и в ней существует звено, в котором деление осуществляется нацело. Докажем, что полином $r_{k} (x)$ является наибольшим общим делителем полиномов $f_{0} (x)$ и $f_{1} (x)$.
Действительно, поскольку $r_{k-1} \vdots r_{k} $, то оба слагаемых в правой части соотношения $r_{k-2} =r_{k-1} q_{k} +r_{k}$ делятся на $r_{k} (x)$, поэтому $r_{k-2} \vdots r_{k}$. Продолжая подобные рассуждения и передвигаясь по цепочке, получаем, что $f_{1} \vdots r_{k} $, $f_{0} \vdots r_{k} $. Таким образом, $r_{k} (x)$ является общим делителем полиномов $f_{0} (x)$ и $f_{1} (x)$.
Пусть $d(x)$ — произвольный общий делитель указанных полиномов. В силу первого равенства цепочки $f_{0} =f_{1} q_{1} +r_{1}$ остаток от деления $r_{1} (x)$ делится нацело на полином $d(x)$. Тогда из второго равенства $f_{1} =r_{1} q_{2} +r_{2} $ следует, что $r_{2} \vdots d$. Рассуждая аналогично и перебирая последовательно все равенства, в итоге имеем $r_{k} \vdots d$. В силу произвольности $d(x)$ и в соответствии с определением НОД получаем, что $r_{k} (x)$ — наибольший общий делитель полиномов $f_{0} (x)$ и $f_{1} (x)$.
В соответствии с алгоритмом Евклида $d(x)=r_{k} (x)$. Но $r_{k} =r_{k-2} -r_{k-1} q_{k} =a_{1}^{(k-2)} r_{k-2} +a_{2}^{(k-1)} r_{k-1}$, где $a_{1}^{(k-2)} =1$, $a_{2}^{(k-1)} =-q_{k} $.
Из алгоритма Евклида следует, что $r_{k-1} =r_{k-3} -r_{k-2} q_{k-1}$. Поэтому, подставляя в выражение для $r_{k}$, получаем $r_{k} =a_{1}^{(k-2)} r_{k-2} +a_{2}^{(k-1)} [r_{k-3} -r_{k-2} q_{k-1} ]= a_{1}^{(k-3)} r_{k-3} +a_{2}^{(k-2)} r_{k-2} $, где $a_{1}^{(k-3)} =a_{2}^{(k-1)} $, $a_{2}^{(k-2)} =a_{1}^{(k-2)} -a_{2}^{(k-1)} q_{k-1} $.
Далее заменяем $r_{k-2} $ и т.д. В итоге будем иметь, что $r_{k} =a_{1}^{(1)} r_{1} +a_{2}^{(2)} r_{2} $. Но $r_{1} =f_{0} -f_{1} q_{1} $, а $r_{2} =f_{1} -r_{1} q_{2} =f_{1} -(f_{0} -f_{1} q_{1} )q_{2} $.
Поэтому окончательно имеем $r_{k} =a_{1}^{(1)} (f_{0} -f_{1} q_{1} )+a_{2}^{(2)} [f_{1} -(f_{0} -f_{1} q_{1} )q_{2} ]=u_{0} f_{0} +u_{1} f_{1},$ где $u_{0} =a_{1}^{(1)} -a_{2}^{(2)} q_{2} $, $u_{1} =-a_{1}^{(1)} q_{1} +a_{2}^{(2)} (1+q_{1} q_{2} )$.
Так как $f_{0} (x)$ и $f_{1} (x)$ взаимно просты, то существуют такие полиномы $u_{0} (x)$ и $u_{1} (x)$, что справедливо $u_{0} (x)f_{0} (x)+u_{1} (x)f_{1} (x)=1$. Умножим обе части последнего соотношения на $f_{2} (x)$, получаем $[u_{0} (x)f_{2} (x)]f_{0} (x)+u_{1} (x)[f_{1} (x)f_{2} (x)]=f_{2} (x)$. Если предположить, что полиномы $f_{0} (x)$ и $f_{1} (x)f_{2} (x)$ имеют общий делитель положительной степени, то он должен быть делителем и полинома $f_{2} (x)$. Но по условию $f_{0} (x)$ взаимно прост с $f_{2} (x)$, следовательно, полином $f_{0} (x)$ и произведение $f_{1} (x)f_{2} (x)$ являются взаимно простыми полиномами.
Поскольку $f_{0} (x)$ и $f_{1} (x)$ взаимно просты, то существуют такие полиномы $u_{0} (x)$ и $u_{1} (x)$, что справедливо $u_{0} (x)f_{0} (x)+u_{1} (x)f_{1} (x)=1$. Умножим обе части соотношения на $f_{2} (x)$, получаем $[u_{0} (x)f_{2} (x)]f_{0} (x)+u_{1} (x)[f_{1} (x)f_{2} (x)]=f_{2} (x)$. Левая часть последнего равенства, очевидно, делится нацело на $f_{0} (x)$. Следовательно, должна делиться нацело и правая часть, т. е. $f_{2} \vdots f_{0}$.