【算法】扩展欧几里得算法
一、欧几里得算法
我们前面学过求最大公约数的算法：欧几里得算法（又叫辗转相除法） ，一般缩写是gcd，在C++中经常写成如下形式：
int gcd(int a,int b) { if(a%b==0) return b; else return gcd(b,a%b); }原理就是代码中比较核心的 gcd(b，a%b)，这个定理用文字描述就是:
用a除以b（这里是a>b,当然，在程序编程中，求两个数的最大公约数，可以不限a和b的大小，a<b也就是多一次循环）得到结果q和余数r，再用除数b除以余数r 再得到一个余数，再用除数除以余数，…如此循环，直到余数为0，那么此时的除数就是最大公因数。
想要证明gcd(a,b) = gcd(b,a%b)，需要简单了解下面两个引理：
若d是a和b的公约数，那么d也是b和c的公约数（c为a%b）
若d是b和c的公约数（c为a%b），那么d也是a和b的公约数
这两个引理的是什么意思呢，拿第一个来说；
假设一个数d是a的因子，也就是a=m*d，同时也是b的因子，b=n*d，那么a%b = a-w*b = (m-w*n)*d；
由此可得，a的因子集合、b的因子集合和c的因子集合是相同的；
然后利用上述定理当余数为0的时候，除数就是最大公约数；
二、扩展欧几里得算法
从字面上看，扩展欧几里得算法就是把欧几里得算法进行了扩展，不仅能求a和b的最大公约数，还其他功能，比如:
求ax+by=m的任意一组解，最小整数解。
求模逆元（模反元素）
为了了解学习上面的公式，需要先了解一个裴属定理