扩展欧几里德算法

扩展欧几里德算法是用来在已知a,b求解一组x，y，使它们满足贝祖等式：ax+by=gcd(a,b)=d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：