拓展欧几里得算法

随便写写……

今天在做作业时遇到了一个问题，关于通过拓展欧几里得算法来求得乘法逆元。

在翻书的时候，发现书上的扩欧是这样写的：

def egcd(a,b):
    r0,r1,s0,s1=1,0,0,1
    while(b):
    q,a,b=a/b,b,a%b
    r0,r1=r0,r0-q*r1
    s0,s1=s1,s0-q*s1
return a,r0,s0

很直观地实现了手写时的矩阵形式

先写成

的格式

在对矩阵最右的进行的运算，用第一行减去第二行作为新的第二行，原来的第二行就变为新的第一行。

即代码中的便是第一行变为第二行，直观点来看就是原本是的得到，这不就是开始时的第二行吗；

那么下一步的也是同理。

这样子算得到的结果没有问题，那如果继续下一步的话运算就会出问题……（未完待续）