<分区>
欧几里得算法的扩展
我们已经知道，对于任意两个整数 a 和 b，存在整数 s 和 t 使得 as + bt = gcd(a,b)。换句话说，gcd(a,b) 是 a 和 b 的线性组合。 gcd(a,b) 是两个整数的最小正组合。 a 和 b 本身表示为普通组合:a = 1· + 0·b 和 b = 0·a + 1·b。从这两个开始，欧几里德算法的扩展找到了 s 和 t，它们的存在迄今为止仅以形式化的方式建立。
将两个线性组合写在一列中，并将欧几里得算法的一步应用于左侧。假设 a = bp + r。将第二个方程乘以 p，然后从第一个方程中减去它: a = 1·a + 0·b b = 0·a + 1·b r = 1·a + (-p)·b
对最后两个等式应用相同的程序。以这种方式继续，直到左边的 Euclid 算法停止。右边就是我们要的线性组合。让我们用一个例子来验证一下:令 a = 2322，b = 654。我采用了求解线性方程的通常惯例，并省略了线性组合中的所有项，但左侧和右侧的两个系数除外。将结果放入表中，第四列等于 p(来自 a = bp + r，每一步都会变化。将 p 左侧的三个数字乘以 p，然后从它们正上方的数字中减去它们。记录结果在下一行。
int algoritmoeuclides(int a,int b)
if (a%b==0)
return b;
return algoritmoeuclides(b,a%b);
}
int main(array<System::String ^> ^args)
{
int a=525;
int b=231;
printf("%d",algoritmoeuclides(a,b));
getch();
}
到目前为止，这是我的代码，它运行完美。问题是当我试图找到 s 和 t 时。我不知道如何找到它，我在论坛上搜索过，但我知道编写此算法以查找 S 和 T 的最佳方法是什么。 我把所有的解释都给了你们一个想法。 PD:抱歉我的英语不好，我不会说英语。任何想法都会受到赞赏。