欧几里得算法（辗转相除法），扩展欧几里得算法，乘法逆元，最小正整数解

欧几里得算法

欧几里得算法是用来求解两个不全为0的非负整数m和n的最大公约数的一个高效且简单的算法。该算法来自于欧几里得的《几何原本》。数学公式表达如下：

对两个不全为0的非负整数不断应用此式：gcd(m,n)=gcd(n,m mod n);直到m mod n为0时。m就是最大公约数

证明：我们假设有a,b两个不全为0的数，令 a % b = r； 那么有 a = kb + r. 假设a,b的公约数是d。记做 d|a,d|b，表示d整除a和b。r = a - kb; 给这个式子两边同除以 d,有 r/d = a /d - kb / d，由于d是a ,b的公约数，那么r/d 必将能整除，即：b 和 a%b的公约数也是d。故：gcd(a,b) = gcd(b, a % b)。到此为止，已经证明了a和b的公约数和 b 和 a % b的公约数相等。直到a mod b为0的时候（因为即使 b > a,经过 a % b后，就变成计算gcd(b,a)。因此，a mod b的值会一直变小，最终会变成0），此时gcd(m,0) = m。因为0除以任何数都是0，所以m是gcd(m,0)的最大公约数。根据上面已经证明的等式gcd(a,b) = gcd(b, a % b)。可得：m就是最大公约数。定理得证。

下面是C++代码实现欧几里得算法。

#include <iostream>
using namespace std;
int gcd(int m, int n);
int main()
{
	int m, n;
	cout << "请输入要计算的两个数，用空格隔开:\n";
	cin >> m >> n;
	cout << "最大公约数是：" << gcd(m, n);
	
	return 0;
}
int gcd(int m, int n)
{
	int r;
	while (0 != n)
	{
		r = m % n;
		m = n;
		n = r;
	}
	return m;
}

扩展欧几里得算法

欧几里得算法提供了一种快速计算最大公约数的方法。而扩展欧几里得算法不仅能够求出其最大公约数。而且能够求出m,n和其最大公约数构成的不定方程mx+ny=d的两个整数x,y(这里x和y不一定为正数)。

在欧几里得算法中，终止状态是n == 0时，这时候其实就是gcd(m,0)；我们想从这个最终状态反推出刚开始的状态。由欧几里得算法可知。gcd(m,n) = gcd(n,m mod n);那么有如下表达式：

gcd(m,n) = m*x1+n*y1;

gcd(n,m mod n) = n*x2+(m - m/n*n)*y2；（此处的m/n表示整除，例如：6/4 = 1；所以：m mod n = m % n = m - m/n*n）

化简上式有：n*x2 + m * y2 - m/n*n*y2

= m*y2 + n*(x2 - m/n*y2)

与原式 gcd(m,n) = m*x1+n*y1;​​​​​​对比，容易得出：

x1 = y2;

y1 = x2 - m/n*y2;

根据上面的递归式和欧几里得算法的终止条件n == 0,我们可以很容易知道最终状态是m * x1 + 0 * y1 = m;故：x1 = 1;根据上述的递推公式和最终状态，可以写出代码如下：

#include<iostream>

using namespace std;
int exgcd(int m, int n, int &x, int &y);

int main()
{
	int x, y;
	int m, n;
	int gcd;
	cout << "请输入两个数字：\n";
	cin >> m >> n;
	cout << "满足贝祖等式" << m << "*x + " << n << "*y = " << (gcd = exgcd(m, n, x, y)) << endl;
	cout << "最大公约数是：" << gcd << endl;
	cout << "其中一组解是：x = " << x << "; y = " << y << endl;
	
	system("pause");
	return 0;
}
int exgcd(int m, int n, int &x, int &y)
{
	if (0 == n)		//递归终止条件
	{
		x = 1;
		y = 0;
		return m;
	}
	int gcd = exgcd(n, m%n, x, y);		//递归求解最大公约数。
	int temp = x;
	x = y;						//回溯表达式1：x1 = y2;
	y = temp - m / n * y;		//回溯表达式2：y1 = x1 - m/n * y2;
	return gcd;
}

上述的方程m*x+n*y=gcd(m,n)；这个方程也被称之为“贝祖等式”。它说明了对a，b和它们的最大公约数d之间的线性丢番图方程。一定存在整数x,y使得m*x+n*y=gcd(m,n)成立。从这里也可以得出一个重要推论：

a,b互质的充要条件是方程ax+by = 1必有整数解。

现在来讨论一个更一般的方程：ax + by = c(a,b,c都是整数)。这个方程想要有整数解，那么根据扩展欧几里得算法我们知道，当且仅当m是d = gcd(a,b)的倍数时有解。同时有无穷多组整数解。

我们知道了线性丢番图方程ax + by = c有整数解的条件，并且根据上述算法，也能求出一组丢番图方程的解。但是这组解很可能包含负数。我们通常的需求是最小的特解。也就是这个不定方程的最小正整数解。

一般扩展欧几里得算法有如下应用：

求解乘法逆元

把a*x=1 （ mod p）称为a关于 1 mod p的乘法逆元。 它的解其实就相当于寻找方程 a*x+p*y=1 的解。根据乘法逆元的性质，只有当a与p互素，a关于模p的乘法逆元有解。如果时不互素，则无解。那么这个方程就是a,b互质的充要条件是方程ax+by = 1必有整数解。我们就可以使用扩展欧几里得算法求得其逆元。

int inv(int m, int n, int & x, int & y)
{
	int gcd = exgcd(m, n, x, y);
	if (1 != gcd)		//说明乘法逆元不存在
	{
		return -1;
	}
	else
	{
		return (x + n) % n;		//为了使余数一定为正数
        //模运算系统的特性
	}
}

这样就能求出两个互质的数的逆元了。

最小正整数解

设整数a,b,c；若方程ax+by = c的一组整数解为（x0,y0）;那么它的任意组整数解都可以写成：（x0+kb',y0-ka'）.

其中a' = a / gcd(a,b)；b' = b / gcd(a,b);k取整数即可。

int res(int a, int b, int c ,int &x, int &y)
{
	int gcd = exgcd(a, b, x, y);		//求出最大公约数以及满足等式mx+ny=gcd(m,n)的一组(x,y);
	if (0 != c % gcd)		//如果c不是gcd(m,n)的倍数，该丢番图方程无整数解。
	{
		return -1;			
	}
	x *= c / gcd;			//将x转化为方程ax+by=c的解。
	//先求出x的最小值。根据通解公式x = x0+kb'; b'= b / gcd(a,b);
	b /= gcd;				//求b'
	if (b < 0)
	{	
		b = -b;				//b为负数，则取绝对值
	}
	int r = x % b;			//求出最小整数解
	if (r <= 0)
	{
		r += b;				//求出最小正整数解
	}

	return r;
}