Наибольший общий делитель полиномов

Определение:

Полином [math]\displaystyle{ g(x) }[/math] называется общим делителем двух полиномов $f_{0} (x)$ и $f_{1} (x)$, если $f_{0} \vdots g$, $f_{1} \vdots g$.

Определение:

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

Определение:

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

Лемма:

Наибольший общий делитель двух полиномов определяется с точностью до постоянного сомножителя.

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

Пусть даны два различных наибольших общих делителя $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)$ являются константами.

[math]\displaystyle{ \blacksquare }[/math]

Алгоритм Евклида

Приведем конструктивный способ построения НОД двух полиномов $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)$ — это наибольший общий делитель полиномов $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)$.

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

В соответствии с алгоритмом Евклида $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} )$.

[math]\displaystyle{ \blacksquare }[/math]

Следствие:

Полиномы $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_{0} (x)$ взаимно прост с каждым из полиномов $f_{1} (x)$ и $f_{2} (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_{1} (x)f_{2} (x)$ имеют общий делитель положительной степени, то он должен быть делителем и полинома $f_{2} (x)$. Но по условию $f_{0} (x)$ взаимно прост с $f_{2} (x)$, следовательно, полином $f_{0} (x)$ и произведение $f_{1} (x)f_{2} (x)$ являются взаимно простыми полиномами.

[math]\displaystyle{ \blacksquare }[/math]

Следствие:

Если произведение $f_{1} (x)f_{2} (x)$ делится нацело на полином $f_{0} (x)$, причем $f_{1} (x)$ и $f_{0} (x)$ являются взаимно простыми, то $f_{2} \vdots f_{0} $.

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

Поскольку $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}$.

[math]\displaystyle{ \blacksquare }[/math]

Рис. 1. Алгоритм Евклида для [math]\displaystyle{ f_0=x^4+x^3-2 }[/math] и [math]\displaystyle{ f_1=x^3+x^2-x-1 }[/math]: остаток каждой строки становится делителем следующей; последний ненулевой остаток [math]\displaystyle{ x-1 }[/math] — НОД.

Рис. 2. Обратный ход: подставляя [math]\displaystyle{ r_1=f_0-xf_1 }[/math] в выражение для [math]\displaystyle{ r_2 }[/math], получаем [math]\displaystyle{ x-1=-x\cdot f_0+(x^2+1)f_1 }[/math]. В общем виде [math]\displaystyle{ d=u_0f_0+u_1f_1 }[/math], а при [math]\displaystyle{ d=1 }[/math] полиномы взаимно просты.

---

Конспект: Алгебра и геометрия