拓展欧几里得算法(Extended Euclidean)

作为一只码农每当学习个新知识尤其是数学知识时。我觉得最好得搞清楚它是为了解决一个什么问题。欧几里得算法是为了求两个数的最大公约数 Greatest Common Divisor 后文都以 gcd 简称，而拓展欧几里得算法则可以帮助我们求出倒数的模 如果对这个写法不太熟悉，我们换一种表示就是——已知两个正整数a和n，我们想求一个数e使得a与e的乘积除以n的余数为1。而在大名鼎鼎的RSA算法中就有这样一步需要求倒数的模，并且还多加了一个限制条件即a与n互质。

拓展欧几里得(简称EEA) 人如其名是基于欧几里得算法(EA) 的，那么我们来回顾下小学所学怎么求两个数m,n的最小公约数 如果这个公式还没勾起你的回忆，那么我们来一段计算过程吧。这里我们求39和69的最大公约数

实话说，小时候学只是机械式地记得这个 *** 作。但当看到EA的表达式后发现写作 能够更好地理解它的本质。

一句话为了概括EEA就是求两个数 和 使得

在具体讲怎么求 , 之前我想先介绍为什么它能让我们求得倒数的模。如前面提到的A，B两数互质的情况下我们有 而我们要求的是 所以对等式两边对A取余

下面我们来讲讲怎么一步一步地来求 , 。改写前面求39和69公约数的式子并令

归纳总结，为了求 我们需要 和

所以我们有

其中初始的 这点我们可以当 时 来验证

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

下面是一个使用C语言的实现：

intexGcd(int a,int b,int &x,int &y)

{

    if(b==0)    //当b==0时，得到解

    {

        x=1y=0

        return a

    }

    intr=exGcd(b,a%b,x,y)//递归调用自身，求解

    intt=xx=yy=t-a/b*y

    return r

}

---