欧几里德算法

欧几里德算法也叫辗转相除法

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

证明

a可以表示成a = kb + r（a，b，k，r皆为正整数）

假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。

而r = a - kb，两边同时除以d，r/d=a/d-kb/d，由等式右边可知m=r/d为整数，因此d|r

因此d也是b,a mod b的公约数。

因(a,b)和(b,a mod b)的公约数相等，则其最大公约数也相等，得证。

例子

用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。

For example, to compute gcd(48,18), one proceeds as follows:

\[(48,18)\to (48-18,18)=(30,18)\to (12,18-12)=(12,6)\to (30-18,18)=(12,18)\to (12-6,6)=(6,6).\]

So \(\gcd(48,18)=6\).

Euclid's algorithm

int gcd(a,b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

拓展欧几里得算法

扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式

\[ax+by=\gcd(a,b)\]

通常谈到最大公约数时，我们都会提到一个非常基本的事实：给予二个整数a、b，必存在整数x、y使得ax + by = gcd(a,b)。

有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，而模反元素在RSA加密算法中有举足轻重的地位。

例子

用类似辗转相除法，求二元一次不定方程47x+30y=1的整数解

用初等变换

\[47=1\times30+17,\quad 30=1\times17+13,\quad 17=1\times13+4,\quad 13=3\times4+1,\quad 1=13-3\times4=4\times13-3\times17=4\times30-7\times17=11\times30-7\times47\]

代码

\[(x,y)\to (y,x-aby)\]

int gcdEx(int a,int b,int& x,int& y)
{
    if(b==0)
    {
        x=1,y=0 ;
        return a ;
    }
    int r=gcdEx(b,a%b,x,y);
    /* r = GCD(a, b) = GCD(b, a%b) */
    //初等变换 x,y:
    int t=x ;
    x=y ;
    y=t-a/b*y ;//x-a/b*y
    return r ;
    
}