求最大公约数和最小公倍数的原理

求用C语言求最大公约数的原理和最小公倍数的原理...谢谢

----------------解决方案--------------------------------------------------------
这个帖子好象有人发过
就是用辗转相除

----------------解决方案--------------------------------------------------------

#include <stdio.h>
#include <conio.h>
int main()
{
int min,max;
int temp;
int saveData[2];
clrscr();
scanf("%d %d",&min,&max);
saveData[0]=min,saveData[1]=max; /*保存输入的两个数,以在求最小公倍数用*/
if(max<min) /*使得max中存放较大的数,min存放较小的数*/
{
temp=min;
min=max;
max=temp;
}

while(max%min!=0)
{
temp=min;
min=max%min;
max=temp;
}
printf("最大公约数:%d\n",min);
printf("最小公倍数:%d\n",saveData[0]*saveData[1]/min);
getch();
}

----------------解决方案--------------------------------------------------------

人家要的是原理~

----------------解决方案--------------------------------------------------------
首先要证明gcd(x,y)=gcd(y,x%y)(x>y)
如果x,y的最大公约数是d
那么可以写成;
x=a*d;y=b*d;...........(1)
设x=q*y+r(0<=r<y)......(2);
把(1)的表达式代入(2)可以得到
r=a*d-q*b*d
所以d是y和r的约数,
再假设y,r的最达公约数是c且c!=d;那么 又有
y=q2*c;r=q3*c;.........(4)
把(4)代入到(2)得:
x=q*q2*c+q3*c;
显然与原来d是x和y的最大公约数矛盾:

x=q1*y+r1;(0<=r1<y)
y=q2*r1+r2(0<r2<r1)
.
.
.
ri=qi*r(i+1)+r(i+2) (0<=r(i+2)<r(i+1))//括号里的代表下标
接下来你要发现y>r1>r2.....>ri>....>=0
所以最后余数是逼近0的
这个时候那个除数就是gcd



中文和英文的切换好累啊

----------------解决方案--------------------------------------------------------
哈……太好啦。
我的作业就有这么一道题的。
一直想不通要怎么做！
可以偷偷懒了。
嘿！嘿！嘿！
----------------解决方案--------------------------------------------------------