在原有的gcd算法上改进（肯定的），公式就是：gcd（a, b）=ax + by;
并先求出其特殊值，当 b=0，gcd（a，b）=a。此时 x=1，y=0；
接着就是直接计算，根据欧几里德原理gcd(a,b) = gcd(b,a mod b)，列出两个方程，
即ax1+ by1= gcd(a,b)
bx2+ (a mod b)y2= gcd(b,a mod b)
因为两个式子等号右侧相等，所以两个式子左侧相等
mod = a-[a/b]b;
将式子化简，并且两个与a相乘的数相等，与b相乘的数也相等，即可求的x与y；
扩展gcd类似与方程，且运用数学公式将a与b的最大公约数用方程表示，并和欧几里德原理相结合，用了方程的思想解出了ab的最大公约数，在运算步骤上比gcd省时。
原文：https://www.cnblogs.com/jiqimin/p/10628177.html