问题

代数 >> 线性代数 >> 多项式
Questions in category: 多项式 (Polynomials).

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

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


使用辗转相除法求两个多项式的最大公因式.

设 $f(x)$ 和 $g(x)$ 是两个多项式, 通过带余除法, 经过有限步后总可以使得最后的余式为零. 具体的, 可设

\[
\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}
\]

假设用 Rvec 向量存储 $\{f(x), g(x), r_1(x), r_2(x), \ldots, r_s(x)\}$,  Qvec 向量存储 $q_1(x), q_2(x), \ldots, q_{s+1}(x)$.

上面最后一式为 $r_{s-1}=q_{s+1}r_s$ (以下均省写 $(x)$ ), 将其代入倒数第二式得到 $r_{s-2}$ 关于 $q_j$ 和 $r_s$ 的表达式, 依次类推.

\[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_k$ 都可以用 $q_j$ 和 $r_s$ 来表示. 但我们要找的是 $r_s$ 关于 $f$ 和 $g$ 的线性表示式. (这里的“线性”表示式, 系数并不是常数.)

从倒数第二式出发,

\[
r_s=r_{s-2}-q_s r_{s-1}
\]

如果 $r_{s-2}$, $r_{s-1}$ 能够写成 $f$ 和 $g$ 的线性表示式即可.


\[
\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}
\]

 


将 $r_s$ 表示为 $(k,h)$, 意思是 $kf+hg$. 于是我们有

\[
\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}
\]

因此, 编程的话, 只需通过这些公式, 依次计算 $r_1, r_2, r_3, \ldots$, 直到 $r_s$. 


例子: 设 $f(x)=x^4+3x^3-x^2-4x-3$, $g(x)=3x^3+10x^2+2x-3$, 求 $(f(x),g(x))$, 并求 $u(x), v(x)$ 使

\[(f(x),g(x))=u(x)f(x)+v(x)g(x).\]

 


Remark:

例子来源于 [1] P. 15


References:

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