欧几里得算法求逆元算法（Python如何用欧几里得求逆元）

Python用欧几里得求逆元的方法：

建立一个带参数返回值的函数
    
    
    
    
，编写求逆元的一次算法     


     


     


     


  ，采用递归的方式循环调用函数 




 




 




 




 
，递归直至余数等于零    
    
    
    
  。调用该函数

   

   

   

   

，将需要求的数值带入进去     

     

     

     

 ，执行该函数就可以了

示例代码如下:

defext_gcd(a,b):#扩展欧几里得算法 ifb==0: return1,0,a else: x,y,gcd=ext_gcd(b,a%b)#递归直至余数等于0(需多递归一层用来判断) x,y=y,(x-(a//b)*y)#辗转相除法反向推导每层a    
    
    
    
  、b的因子使得gcd(a,b)=ax+by成立 returnx,y,gcd

执行结果如下：

ext_gcd(1848,701) >>>(-11,29,1)