a可以表示成a = k*b + r（a，b，k，r皆为正整数，且r

假设d1是a,b的一个任一 公约数，即a和b都可以被d1整除。

而r = a - k*b，两边同时除以d1，r/d1=a/d1-k*b/d1=m1，由等式右边可知m1为整数， 因此d也是b,a mod b的公约数。

假设d2是b,a mod b的任一公约数, 则(a mod b)/d2=(a-k*b)/d2=a/d2-k*b/d2=m2，易知m2是一个整数。

进而a/d2=m2+k*d/d2结果为一个整数，因此d2也是a,b的公约数

因此(a,b)和(b,a mod b)的公约数相同，其最大公约数也必然相等，得证。

那么求a，b的最大公约数转换成了求b，a mod b的最大公约数（假设b > b），问题规模变小，可以不断重复以上过程直至某个数变成零，则另一个非零数即为所求。可以归纳为：若a，b全为零则最大公约数不存在，若a、b其中之一为零，则最大公约数为非零那一个；若两个都不为零，则新a=旧b，新b=旧a mod 旧b然后重复，容易看出这是一个递归的过程。

用C语言写的求最大公约数的代码：

#include
int gcd(int num1,int num2)						
{//本函数实现递归求最大公约数
	if(num2==0) return num1;							//若num2为0则num1为最大公约数
	else return gcd(num2,num1%num2);					//否则，改为求num2与num1%num2的最大公约数
}
int main()
{
	int num1,num2;
	int ans;
	while (scanf("%d%d",&num1,&num2)!=EOF)
	{
		if(num1<=0&&num2<=0) 
		{
			printf("输入错误！");
			break;
		}
		if(num1

二、求最小公倍数

知道了如何求最大公约数，那么有没有什么好方法求最大公倍数？

同样设两个非负整数a、b，其乘积k=a*b，又设c为a、b的一个公约数，则有k/c=(a*b)/c=(a/c)*b=a*(b/c)，可知k/c是个整数c语言求最大公约数，且k/c即为a的倍数又是b的倍数（a，b公倍数）c语言求最大公约数，那么要使k/c为最小则c为最大公约数。

因此，只要求得a，b的最大公约数c，则a，b的最小公倍数即为(a*b)/c

黑框运行结果：

后记：

再一次证明学好数学很重要。。