拓展欧几里德算法

拓展欧几里德算法在计算 a,b 的最大公约数的同时,还能找到 x,y,使它们满足贝祖等式 ax + by = gcd(a,b). 以拓展欧几里德算法求得的系数满足贝祖等式的最简系数。

References