辗转相除法求最大公因式

辗转相除法求最大公因式

一、引言

在数学中，尤其是在多项式运算领域，求解两个多项式的最大公因式（GCD, Greatest Common Divisor）是一个重要的问题。辗转相除法，又称为欧几里得算法，是一种高效且易于理解的求解方法。本文将详细介绍如何使用辗转相除法来求解两个多项式的最大公因式。

二、基本概念

1. 多项式：由变量、系数和运算符号（加、减、乘、幂等）构成的代数表达式。例如，$f(x) = x^2 + 3x + 2$ 和 $g(x) = x + 1$ 都是多项式。

2. 最大公因式：两个或多个多项式共有的最大的那个因式。在整数范围内，最大公因数必须是正数；但在多项式范围内，最大公因式可以取正负号中的任意一个。

三、辗转相除法的步骤

1. 选择初始多项式：设两个待求最大公因式的多项式为 $f(x)$ 和 $g(x)$，其中 $deg(f(x)) \geq deg(g(x))$（即 $f(x)$ 的次数不低于 $g(x)$ 的次数）。如果 $deg(g(x)) > deg(f(x))$，则交换两者的位置。

2. 进行第一次除法：用 $f(x)$ 除以 $g(x)$，得到商 $q_1(x)$ 和余数 $r_1(x)$，使得 $f(x) = g(x) \cdot q_1(x) + r_1(x)$。注意，这里的除法是按照多项式长除法进行的。

3. 迭代过程：将 $g(x)$ 和 $r_1(x)$ 作为新的被除数和除数，重复上述除法过程，直到余数为零或者余数的次数小于除数的次数为止。具体地，对于第 $k$ 步（$k \geq 2$），有 $g_{k-1}(x) = g_k(x) \cdot q_k(x) + r_k(x)$，其中 $g_{k-1}(x)$ 是上一步的除数，$g_k(x)$ 是当前的被除数，$q_k(x)$ 是商，$r_k(x)$ 是余数。

4. 确定最大公因式：当余数为零时，最后一步的除数 $g_k(x)$ 就是 $f(x)$ 和 $g(x)$ 的最大公因式。如果余数不为零但次数小于除数的次数，那么此时的除数也是它们的最大公因式（因为此时继续除法只会得到更小的余数，而不会影响最大公因式的结果）。

四、示例

考虑两个多项式 $f(x) = x^4 - 5x^3 + 6x^2 - 2x$ 和 $g(x) = x^3 - 3x^2 + 2x$。

1. 首先，用 $f(x)$ 除以 $g(x)$ 得到： $$ f(x) = (x - 2) \cdot g(x) + (-4x^2 + 8x - 4) $$ 这里，$q_1(x) = x - 2$，$r_1(x) = -4x^2 + 8x - 4$。

2. 然后，用 $g(x)$ 除以 $r_1(x)$ 得到： $$ g(x) = -\frac{1}{4}x \cdot r_1(x) + (x^2 - 2x + 1) $$ 这里，$q_2(x) = -\frac{1}{4}x$，$r_2(x) = x^2 - 2x + 1$。注意到这里我们进行了有理系数的除法，但在实际计算中，我们通常会将整个等式两边都乘以分母（这里是4），以避免分数运算。

3. 最后，用 $r_1(x)$ 除以 $r_2(x)$ 得到： $$ r_1(x) = -4(x - 1) \cdot r_2(x) + 0 $$ 这里，$q_3(x) = -4(x - 1)$，$r_3(x) = 0$。由于余数为零，所以 $r_2(x) = x^2 - 2x + 1$ 就是 $f(x)$ 和 $g(x)$ 的最大公因式。进一步观察可知，$r_2(x) = (x - 1)^2$。

因此，$f(x)$ 和 $g(x)$ 的最大公因式是 $(x - 1)^2$。