拓展欧几里得算法(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公约数的式子并令

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

所以我们有

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

辗转相除法,

又名欧几里德算法乃求两个正整数之最大公因子的算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

就是把上一轮有余数的除法计算中， 除数变为下一轮计算的被除数， 余数变为下一轮计算的除数， 一直这样计算下去， 直到最后一次计算余数为零， 在最后一轮计算中的被除数，即为所求的最大公约数。

举例： 105和85的最大公约数

第一轮计算 105÷85=120

第二轮计算 85÷20=45

第三轮计算 20÷5=4

第三轮没有余数， 因此 105和85的最大公约数就是第三轮计算的被除数 5

至于C语言编程，下边是我自己写的G函数(思想就是辗转相除法求最大公约数)

int G(int x,int y)

{ int t;

while(y!=0)

{ t=x%y ;

x=y;

y=t;

}

return x;

}

以上就是关于拓展欧几里得算法(Extended Euclidean)全部的内容，包括:拓展欧几里得算法(Extended Euclidean)、什么是辗转相除法、欧几里得算法（辗转相除法）等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！