数学--数论--欧几里得定理和拓展欧几里得定理

欧几里得定理:

gcd(a, b) = gcd(b, a%b)

证明： 我们首先约定：m = gcd(a,b) , n = gcd(b, q) , a = b*p +q。（这里的gcd含义跟上面一样，q的含义跟后面式子同）  1.  m 是a,b的最大公约数，那么m整除a,b      q = a - b*p      m也可以整除q     =>m就是b和q的公约数     =>n是b,q的最大公约数     =>n >=m

2. =>n 是q,b的最大公约数，那么n整除q,b     =>a = b*p + q     =>n也可以整除a     =>n就是b和a的公约数     =>m是b,a的最大公约数     =>m >= n

3.q=a%b 综上所述，那么我们可以得出 n = m,及gcd(a, b) = gcd(b ,a%b) 

实现：

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

三目运算符优化：

int gcd(a, b)
{
	return b == 0?a:gcd(b, a%b);
}

拓展欧几里得定理：