Алгоритм Евклида для многочленов

Алгоритм

Так как для многочленов определено деление с остатком, к ним применим алгоритм Евклида для поиска НОД, аналогичный числовому.

1. Разделить $f(x)$ на $g(x)$, получить остаток $r(x)$.

2. Если $r(x)=0$, то НОД равен $g(x)$.

3. Иначе заменить пару $(f,g)$ на $(g,r)$ и повторить шаг 1.

Пусть $f,g\in P[x],\mathrm{deg}(g)\ne 0$

$$\begin{array}{l}f=g\cdot q+r,\mathrm{deg}(r)<\mathrm{deg}(g)\\ g=r\cdot q_1+r_1,\mathrm{deg}\left(r_1\right)<\mathrm{deg}(r)\\ r=r_1\cdot q_2+r_2,\\ \dots \\ r_i=r_{i+1}\cdot q_{i+2}+r_{i+2}\\ \dots \\ r_{s-2}=r_{s-1}\cdot q_s+r_s,r_s\ne 0-\text{последний ненулевой остаток равен}\mathrm{НОД}(f,g)\\ r_{s-1}=r_s\cdot q_{s+1}\end{array}$$

Процесс всегда завершается, так как на каждом шаге степень остатка уменьшается

Пример

$$\begin{array}{rl}& f=x^4+x^3-3x^2-4x-1,g=x^3+x^2-x-1\\ & \\ & x^4+x^3-3x^2-4x-1\mid \underline{x^3+x^2-x-1}\\ & \frac{x^4+x^3-x^2-x}{-2x^2-3x-1=r(x)\text{- остаток на шаге 1}}\end{array}$$

Далее по алгоритму

$$\begin{array}{rl}& \begin{array}{lr}{x}^3+x^2-x-1& \frac{-2x^2-3x-1}{-\frac{1}{2}x+\frac{1}{4}}\\ \underline{x^3+\frac{3}{2}{x}^2+\frac{1}{2}x}& \end{array}\\ & -\frac{x^2}{2}-\frac{3}{2}x-1\\ & \underline{-\frac{x^2}{2}-\frac{3}{4}x-\frac{1}{4}}\\ & -\frac{3}{4}x-\frac{3}{4}=r_1(x)\text{ - остаток на шаге }2\text{, равный НОД }(f,g)\text{, }\end{array}$$

поскольку $r=r_1\cdot \left(-\frac{4}{3}\right)\cdot (2x+1)+r_2(x)$ (при этом $r_2(x)=0,r_1(x)-$ последний ненулевой остаток)
В качестве НОД можно взять этот же многочлен с другим множителем, например,

$$x+1=\left(-\frac{3}{4}x-\frac{3}{4}\right)\cdot \left(-\frac{4}{3}\right)$$