Euclid 算法的扩展
我们已经知道，对于任意两个整数 a 和 b，存在整数 s 和 t，使得 + 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
对最后两个方程应用相同的过程。以这种方式继续，直到左边的欧几里得算法停止。在右边，会有我们所追求的线性组合。让我们用一个例子来检查一下：让 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：对不起我的英语我不是说英语的。任何想法都会受到赞赏。