爱悠闲 > 欧几里得原理及扩展欧几里得原理(Euclidean Theory and Extended Euclidean Theory)学习笔记

欧几里得原理及扩展欧几里得原理(Euclidean Theory and Extended Euclidean Theory)学习笔记

分类: 算法笔记  |  标签: 数论,算法  |  作者: rising_fallmoon 相关  |  发布日期 : 2014-10-28  |  热度 : 733°

题记:这是我第四次复习扩展欧几里得原理,因为不常用到,想要使用的时候又想不起细节,总是要查资料,于是索性这次整理一下欧几里得原理及其扩展原理存档至博客以备查用。

一、欧几里得原理

欧几里得原理(Euclidean Theory)是初等数论中求两正整数最大公约数(Greatest Common Divisor, GCD)的方法。欧几里得原理在中国古代又称“辗转相除法”,这一称法揭示了其求最大公约数的过程。

对于两个正整数a,b,记其最大公约数为gcd (a,b)。

那么我们有 gcd (a,b) = gcd (b,a%b) 

即a与b的最大公约数也是a除以b的余数与b的最大公约数。

欧几里得原理可以通过递归实现,下面给出其实现的C代码:

int gcd(int a, int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
函数返回参数a,b的最大公约数。注意该gcd函数调用时参数a,b不应该同时为0,否则该函数将不存在实际意义。


二、扩展欧几里得原理

欧几里得原理的扩展版本最经典的用法在于求二元一次不定方程的整数解。


(1)先来看一个最简单的二元一次不定方程:

a*x + b*y = 1     (*),且 gcd (a,b) = 1,设它的一组整数解为 x = x1, y = y1。

对于另一个二元一次不定方程:

b*x + (a%b)*y = 1    (**),设它的一组整数解为 x = x2, y = y2。

那么我们可以得到 a*x1 + b*y1 = b*x2 +(a%b)*y2 = 1,又因为 a%b = a - a/b*b,带入前式,

我们可以得到 a*x1 + b*y1 = a*y2 + b*(x2-a/b*y2),由于a,b是任意的互质正整数,故可由该式得到方程(*)与方程(**)的解的关系如下:

x1 = y2,

y1 = x2-a/b*y2,即方程(*)的解可由方程(**)的解得到。

若我们想要求得a*x + b*y = 1的解,可以先求b*x + (a%b)*y = 1的解。我们可以发现这两个方程其未知量x,y 的系数之间是“辗转相除”的关系。那么最终我们只需要求gcd (a,b)*x + 0*y = 1的解(这里gcd (a,b) = 1,其解为 x = 1,y任意,一般取0),逆推之就可得到原方程的解。而逆推的过程就是扩展欧几里得原理的过程。


(2)我们现在已经解决了求二元一次不定方程 a*x + b*y = 1, gcd (a,b) = 1的解。下面考察二元一次不定方程的一般情况:

对于一般的二元一次方程 m*x + n*y = t,

  • 若gcd (m,n) | t,亦即 t%gcd(m,n) == 0,方程的解将与方程 (m/gcd(m,n))*x + (n/gcd(m,n))*y = t/gcd(m,n) 的解相同。记新方程为 a*x + b*y = d,那么其解将是方程 a*x + b*y = 1的d倍。而方程 a*x + b*y = 1, gcd(a,b) = 1的解在(1)中已经求得。
  • 否则方程无整数解

上述过程即用扩展欧几里得原理求一般二元一次不定方程整解的过程。