1.回顾辗转相除法求最大公倍数： 

（辗转相除法和下面所讲到的算法里面的m和n没什么关系可正可负 更没有大小关系的区分）

 return a; // b=0 满足关系跳出循环此时a的值就是最大公约数

a.求②元一次方程的一组特解：

 } //调用的函数运行顺序
 

 
 

?首先可以肯定它一定有解且解的数量无限
?我们可以找出式子可以加减的最小元 即最小公倍数lcm
 

 
 

 
 

 
 

 
 

   计算②式特解的方法：  先算出①式的特解 然后将x和y同时乘于6 / gcd（38，8）就能得到一组特解；
 
 

 
 

 //用于解决ax+by=c类的求最小整数解 
 

 


 

 注：替代pow函数pow函数是浮点型时候才用的 如果用在int或其他上可能会错误，qpow（快速幂）不仅运算快而且更精确！
 


 

 


 

 } //整个循环要放在while里面进行多次计算

 

 注： a和p只囿在互素的情况下才存在逆元
 
 

 1.快速幂+费马小定理/欧拉方程：
 
 

 （a^(mod-2)+函数中取余mod的结果表示逆元）
 
 

 
 

 

 2. 拓展欧几里得求逆元：
 
 

 （a和b=mod求特解表示逆元）