1.欧几里得算法

欧几里得算法， 又名辗转相除法求最大公约数的一种方法。
基于 gcb(a,b)=gcb(b,a%b) 这个定理，用较大数除以较小数，再用出现的余数（第一余数）去

例如：
求 10 ，25的最大公约数：
25 / 10 = 2 ······5
10 / 5 = 2 ······0
所以10，25的最大公约数为5

2. 证明

不妨设a>b 且a=kb+r，其中k为a除以b的商,r为余数
任取a和b的公约数d，则有a=xd, b=yd
	r=a-kb=xd-kyd=(x-ky)d,即d为r的约数
又因：d为b的约数
	所以：d为b和r的公约数，即d为 a%b和 b 的公约数
由d的任意性，所以有①a和b的所有公约数均是 a%b和b的公约数
由a=kb+r=kb+a%b,同理亦可证
				 ②a%b和b的公约数均是a和b的公约数
综合①②可得：
	a和b的所有公约数等价于a%b和b所有的公约数，a和b的最大公约数等价于a%b和b最大的公约数，得证.
	
1
2
3
4
5
6
7
8
9
10
11

3.代码

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

4.最小公倍数

最小公倍数为：
lcm(a,b)=ab/gcb(a,b)
代码中为了防止ab过大超范围，通常先除gcb(a,b)，即 lcm(a,b)=a/gcb(a,b)*b

5.最小公倍数证明：

1.文氏图法
定义A：a分解质因数
定义B：b分解质因数
显然，A∩B为 最大公约数，AUB为最小公倍数，
AUB=A的所有元素+B的所有元素-AUB=ab/gcb(a,b)

2.数论证明

3.其他证明