欧几里得算法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

证明
记a|d表示a可以整除d(d为a的倍数)
设d为a和b的公约数，即d|a，d|b。
a mod b = a-kb，显然d也为a mod b 的和b的公约数。

设d为a mod b和b的公约数，即d|b，d|(a mod b)
则有d|(a-kb)，因为\(\frac{a}{d}-k\frac{b}{d}\)和\(\frac{b}{d}\)为整数，所以\(\frac{a}{d}\)必为整数，即d也为a和b的公约数。

综上，(a,b)与(b,a mod b)有相同的公约数，故其最大公约数也相等。

C++实现

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);//其实b比a大时也是对的
}

扩展欧几里得算法

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

证明
我们先假设\(ax+by=gcd(a,b)\)①存在整数解，令\(r=a\%b\)，
根据假设我们又可以得到个式子：
\(bx^{\prime}+ry^{\prime}=gcd(b,r)=gcd(a,b)\)存在整数解，将\(r=a-\lfloor \frac{a}{b} \rfloor b\)带入并整理
得：\(b(x^{\prime}-\lfloor \frac{a}{b} \rfloor y^{\prime})+ay^{\prime}=gcd(a,b)\)②
我们发现①②具有相同的形式，即①式的解可以从②式中获得：
\(x=y^{\prime},y=x^{\prime}-\lfloor \frac{a}{b} \rfloor y^{\prime}\)
这就是说只要我们找到②式的解，就能得到①式(上一层)的解。
根据相同的形式，从②式的原式我们又可以得到\(rx^{\prime\prime}+r^{\prime}y^{\prime\prime}=gcd(r,r^{\prime})=gcd(a,b),r^{\prime}=b\%r\)...
根据欧几里得，这个过程会有一个尽头：
\(dx+0y=gcd(a,b)\)，其中\(d=gcd(a,b)\)，为使等式成立，我们可以令\(x=1,y=0\)(当然也可以为其他值)
这就找到了一组可行解，在一层层倒退回去，就能得到原始方程的一组整数解。

C++实现

int exgcd(int a,int b,int &x,int &y){
    //x为a的解，y为b的解
    if(b==0){//到达尽头
        x=1,y=0;
        //y可赋任意整数值
        return a;//返回最大公因数
    }
    int d=exgcd(b,a%b,x,y);
    //此时的x,y为下一层的解
    int temp=y;
    y=x-a/b*y;//把y变成当前层解
    x=temp;//把x变成当前层解
    return d;
}