《数论与代数的计算性导论》 华南师范大学 王立斌
欧几里德算法计算两个非零整数a和b的最大公因子，而扩展欧几里德算法（extendedEuclidean algorithm ，简记为 egcd 算法）不但计算出最大公因子，还同时计算出这个公因子如何表达为 a 和 b 的线性组合。

C++实现：
（使用visual studio 2019）

#include<iostream>
using namespace std;
int main()
{
	void EGCD(int a, int b);
	int a, b;
	cin >> a >> b;
	EGCD(a, b);
	return 0;
}
void EGCD(int a,int b)
{
	int r0 = 1, r1 = 0, s0 = 0, s1 = 1;
	while (b)
	{
		int q = a / b;
		int temp1 = a;
		a = b; b = temp1 % b;
		int temp2 = r0;
		r0 = r1; r1 = temp2 - q * r1;
		int temp3 = s0;
		s0 = s1; s1 = temp3 - q * s1;
	}
	cout << "gcd=" << a << endl;
	cout << "r=" << r0 << endl;
	cout << "s=" << s0 << endl;
}

测试：

65×7-450=5

369×（-223）+4572×18=9