Question

# 问题

Questions in category: 多项式 (Polynomials).

## [算法]利用辗转相除法求两个多项式的最大公因式

Posted by haifeng on 2023-03-25 15:33:12 last update 2023-03-27 21:33:22 | Answers (2) | 收藏

\begin{aligned} f(x)&=q_1(x)\cdot g(x)+r_1(x),\\ g(x)&=q_2(x)\cdot r_1(x)+r_2(x),\\ r_1(x)&=q_3(x)\cdot r_2(x)+r_3(x),\\ r_2(x)&=q_4(x)\cdot r_3(x)+r_4(x),\\ &\vdots\\ r_{s-3}(x)&=q_{s-1}(x)\cdot r_{s-2}(x)+r_{s-1}(x),\\ r_{s-2}(x)&=q_{s}(x)\cdot r_{s-1}(x)+r_{s}(x),\\ r_{s-1}(x)&=q_{s+1}(x)\cdot r_s(x)+0. \end{aligned}

$r_{s-1}=q_{s+1}r_s$

$r_{s-2}=q_s (q_{s+1}r_s)+r_s=(q_s q_{s+1}+1)r_s$

$\begin{split} r_{s-3}&=q_{s-1}\cdot r_{s-2}+r_{s-1}\\ &=q_{s-1}(q_s q_{s+1}+1)r_s+q_{s+1} r_s\\ &=(q_{s-1}q_s q_{s+1}+q_{s-1}+q_{s+1})r_s \end{split}$

$r_s=r_{s-2}-q_s r_{s-1}$

$\begin{split} r_1&=f-q_1 g\\ r_2&=g-q_2 r_1=g-q_2(f-q_1 g)=-q_2 f+(1+q_2 q_1)g\\ r_3&=r_1-q_3 r_2=(f-q_1 g)-q_3(-q_2 f+(1+q_2 q_1)g)\\ &=(1+q_3 q_2)f+(-q_1-q_3(1+q_2 q_1))g\\ r_4&=r_2-q_4 r_3=\bigl(-q_2 f+(1+q_2 q_1)g\bigr)-q_4\cdot\Bigl[(1+q_3 q_2)f+(-q_1-q_3(1+q_2 q_1))g\Bigr]\\ &=\Bigl[-q_2-q_4(1+q_3 q_2)\Bigr]f+\Bigl[(1+q_2 q_1)+q_4(q_1+q_3(1+q_2 q_1))\Bigr]g\\ r_5&=r_3-q_5 r_4=\bigl((1+q_3 q_2)f+(-q_1-q_3(1+q_2 q_1))g\bigr)\\ &\qquad-q_5\biggl(\Bigl[-q_2-q_4(1+q_3 q_2)\Bigr]f+\Bigl[(1+q_2 q_1)+q_4(q_1+q_3(1+q_2 q_1))\Bigr]g\biggr)\\ &=\biggl[(1+q_3 q_2)+q_5\bigl(q_2+q_4(1+q_3 q_2)\bigr)\biggr]f+\biggl[\bigl(-q_1-q_3(1+q_2 q_1)\bigr)+(1+q_2 q_1)+q_4\bigl(q_1+q_3(1+q_2 q_1)\bigr)\biggr]g\\ \end{split}$

$\begin{split} r_1&=(1,-q_1)\\ r_2&=(0,1)+(-q_2)(1,-q_1)=(-q_2, 1+q_2 q_1)\\ r_3&=(1,-q_1)+(-q_3)\cdot(-q_2, 1+q_2 q_1)=(1+q_3 q_2, -q_1-q_3(1+q_2 q_1))\\ r_4&=(-q_2, 1+q_2 q_1)-q_4(1+q_3 q_2, -q_1-q_3(1+q_2 q_1))\\ &=(-q_2-q_4(1+q_3 q_2), 1+q_2 q_1+q_4(q_1+q_3(1+q_2 q_1))) \end{split}$

$(f(x),g(x))=u(x)f(x)+v(x)g(x).$

Remark:

References:

[1] 北京大学数学系几何与代数教研室代数小组 编《高等代数》, 高等教育出版社. 2000 年.