Просмотр кода страницы Наибольший общий делитель полиномов

{{Определение
|definition=Полином <math>g(x)</math> называется '''общим делителем''' двух полиномов $f_{0} (x)$ и $f_{1} (x)$, если $f_{0} \vdots g$, $f_{1} \vdots g$.
}}

{{Определение
|definition=Общий делитель $d(x)$ полиномов $f_{0} (x)$ и $f_{1} (x)$ называется '''наибольшим общим делителем''' (НОД), если $d(x)$ делится нацело на любой другой общий делитель этих полиномов.
}}

{{Определение
|definition=Полиномы $f_{0} (x)$ и $f_{1} (x)$ называются '''взаимно простыми''', если они не имеют общих делителей положительных степеней.
}}

{{Лемма
|statement=Наибольший общий делитель двух полиномов определяется с точностью до постоянного сомножителя.
|proof=Пусть даны два различных наибольших общих делителя $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)$.

{{Теорема
|statement=Если $d(x)$ {{---}}  это наибольший общий делитель полиномов $f_{0} (x)$ и $f_{1} (x)$, то существуют такие полиномы $u_{0} (x)$ и $u_{1} (x)$, что
$d(x) = u_{0} (x)f_{0} (x)+u_{1} (x)f_{1} (x)$.  
|proof=В соответствии с алгоритмом Евклида $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} )$.
}}

{{Следствие
|statement=Полиномы $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$.  
}}

{{Следствие
|statement=Если полином $f_{0} (x)$ взаимно прост с каждым из полиномов $f_{1} (x)$ и $f_{2} (x)$, то он взаимно прост и с их произведением $f_{1} (x)f_{2} (x)$.
|proof= Так как $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)$ являются взаимно простыми полиномами.
}}

{{Следствие
|statement=Если произведение $f_{1} (x)f_{2} (x)$ делится нацело на полином $f_{0} (x)$, причем $f_{1} (x)$ и $f_{0} (x)$ являются взаимно простыми, то $f_{2} \vdots f_{0} $.
|proof= Поскольку $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}$.
}}