扩展欧几里得算法
维基百科,自由的 encyclopedia
扩展欧几里得算法(英语:Extended Euclidean algorithm)是欧几里得算法(又叫辗转相除法)的扩展。已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,找到整数x、y(其中一个可能是负数),使它们满足贝祖等式。[1]如果a是负数,可以把问题转化成(为a的绝对值),然后令。
在欧几里得算法中,我们仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商,在辗转相除的同时也能得到贝祖等式[2]中的x、y两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。
另外,扩展欧几里得算法是一种自验证算法,最后一步得到的和(和的含义见下文)乘以后恰为和,可以用来验证计算结果是否正确。