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

Алгоритм

Алгоритм поиска наибольшего общего делителя многочленов $f$ и $g$
Пусть $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}$

Теорема о наибольшем общем делителе

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

Теорема

$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$ )

многочлены

Ссылка на оригинал

---

Пример

Пример

\begin{aligned} & f=x^{4}+x^{3}-3 x^{2}-4 x-1, \quad g=x^{3}+x^{2}-x-1 \\ \\ & x^{4}+x^{3}-3 x^{2}-4 x-1 \quad \mid \underline{x^{3}+x^{2}-x-1} \\ & \frac{x^{4}+x^{3}-x^{2}-x}{-2 x^{2}-3 x-1 =r(x) \text{- остаток на шаге 1}} \\ \end{aligned}$$ Далее по алгоритму

\begin{aligned}
& \begin{array}{lr}
x^3+x^2-x-1 & \frac{-2 x^2-3 x-1}{-\frac{1}{2} x+\frac{1}{4}} \
\underline{x^3+\frac{3}{2} x^2+\frac{1}{2} x} &
\end{array} \
\quad & -\frac{x^2}{2}-\frac{3}{2} x-1 \
\quad & \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{aligned}

поскольку $r=r_{1} \cdot\left(-\frac{4}{3}\right) \cdot(2 x+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)$$

многочлены