在线计算器: 扩展欧几里得算法

本网站已经有两个整数的最大公约数, 它使用欧几里得算法。
结果(对我来说)，存在一个扩展的欧几里得算法。该算法除了计算整数a和b的最大公约数外，还计算贝祖恒等式系数，即整数x和y达到
$ax + by = {\rm gcd} (a, b)$

所以它允许用a和b的最大公约数来计算它们的商。

你可以像往常一样看到下面的计算器，而理论在计算器下面。

第一个整数

第二个整数

最大公约数

较大整数的系数

较小整数的系数

扩展算法使用递归，并在其回溯中计算系数。计算的公式可以从以下考虑得到:

对 $(b\%a,a)$ , 已知系数 $(x_1,y_1)$ ，如：

$(b \% a)x_1 + ay_1 = g$ ,

我们需要计算 $(a,b)$ 的系数, 如:

$ax + by = g$

首先,我们用下面的等式替换 $b\%a$ :

$b\%a = b - \left\lfloor \frac{b}{a} \right\rfloor a$ , 在此

$\left\lfloor \frac{b}{a} \right\rfloor$ - 从b到a的整数除法的商，

将它代入下式:

$g = (b \% a) x_1 + a y_1 = \left( b -\left\lfloor \frac{b}{a} \right\rfloor a\right) x_1 + ay_1$

然后，整理后我们得到:

$g = bx_1 + a \left( y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1\right)$

通过与初始方程比较，我们可以将x和y表示为:

$x = y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1$
$y = x_1$

递归回溯的开始是欧几里得算法的结束，此时a=0，GCD=b，所以首先x和y分别为0和1。进一步的系数是用上述公式计算的。

PLANETCALC 在线计算器