一、求最大公因子
设a,b是任意两个正整数，将他们的最大公因子gcd(a,b)简记为(a,b)。
重要的结论如下所示：
(a,b) = (b,a mod b)
a mod b 可以理解为a与b相除之后所得的余数，听上去有点抽象，我们可以通过简单的例子来理解。
例如：
(55,22)=(22,55 mod 22) = (22,11) = (11,0) = 11
就可以简单的理解为
55 = 22*2 + 11
22 = 11*2 + 0
通过上述简单的例子，我们就可以掌握辗转相除法，伪代码如下所示：
EUCLID(a,b)
1.X <--- a; Y <--- b;
2.if Y=0 then return X = (a,b);
3.if Y=1 then return Y = (a,b);
4.R = X mod Y;
5.X = Y;
6.Y = R;
7.goto 2.
当然，上面伪代码提供的只是算法的实现，我们可以使用Python代码简单实现
def gcd(a,b):
if a二、求乘法逆元
如果 推广的欧几里得算法先求出 其实，此算法并没有我们想象中那么可怕，我们可以简单的理解为 就拿 所以 当然，上面伪代码提供的只是算法的实现，我们可以使用 欢迎分享，转载请注明来源：内存溢出(a,b) = 1，则b在mod a下有乘法逆元（不妨设b），即存在一个x(x,使得bx = 1 mod a。（a,b）,当（a,b）= 1时，则返回b的逆元。
算法使用伪代码表示为：EXTENED EUCLID(a,b)(设bX1，X2的初始值分别为1，0；Y1，Y2的初始值分别为0，1；a,b非别是我们所要求的两个未知数；当然这里有个小细节就是（b < a）.
初始值赋值完毕后
(1)我们进行判断Y3的值，如果等于0，返回X3 =（a,b）直接就没有乘法逆元 ；如果Y3等于1，返回Y3 =（a,b），Y2就是b的乘法逆元;
(2)如果都不满足前面的判断，那么Q等于X3除以Y3，T1 = X1-QY1，T2 = X2-QY2，T3 = X3-QY3，X1 = Y1，X2 = Y2，X3 = Y3 ，Y1 = T1，Y2 = T2，Y3 = T3
(3)其实(2)中的判断就是循环，循环结束就得看Y3的值，这又用到(1)的判断方法(1769,550)来举例循环次数 Q X1 X2 X3 Y1 Y2 Y3 初值 —— 1 0 1769 0 1 550 1 3 0 1 550 1 -3 119 2 4 1 -3 119 -4 13 74 3 1 -4 13 74 5 -16 45 4 1 5 -16 45 -9 29 29 5 1 -9 29 29 14 -45 16 6 1 14 -45 16 -23 74 13 7 1 -23 74 13 37 -119 3 8 4 37 -119 3 -171 550 1 (1769，550）= 1，550^-1 mod 1769 = 550Python代码简单实现def Eu_kz(m,b):
if m < b:
t = m
m = b
b = t
x1,x2,x3 = 1,0,m
y1,y2,y3 = 0,1,b
while True:
if y3==0:
return None
break
elif y3==1:
return y2%m
break
else:
Q = x3//y3
t1,t2,t3 = x1-Q*y1,x2-Q*y2,x3-Q*y3
x1,x2,x3 = y1,y2,y3
y1,y2,y3 = t1,t2,t3
m = int(input("m="))
b = int(input("b="))
r = Eu_kz(m,b)
print(r)
PS：一开始接触辗转相除法和乘法逆元可能会有点困难，但是不要担心，多思考一会儿，一定可以理解的，如果算法理解上存在问题或困难欢迎评论区留言或私信我，感谢支持！！！
微信扫一扫
支付宝扫一扫
评论列表（0条）