如何找到euclide算法的s和t

Question

欧几里得算法的推广

我们已经知道,对于任何两个整数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.从这两个开始,Euclid算法的扩展找到了s和t,其存在迄今仅以正式方式建立.

在列中写下两个线性组合,并将Euclid算法的一步应用到左侧.假设a = bp + r.将第二个等式乘以p并从第一个等式中减去它:a = 1·a + 0·b b = 0·a + 1·b r = 1·a +( - p)·b

对最后两个方程应用相同的过程.以这种方式继续,直到左边的Euclid算法停止.在右边,将有我们追求的线性组合.让我们用一个例子来检查:a 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时.我不知道如何找到它,我在论坛上搜索但是idk是最好的方法来编程这个算法找到S和T.我把所有的解释给你们一个想法.PD:对不起,我的英语不是讲英语的人.任何想法都是一个先例.

Answer 1

干得好

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm