谁能用通俗易懂的方法简述下什么是辗转相除法,我知道最小公约数和最大公倍数的原理.12,8；最大公约数是4,最小公倍数是24；那余数4莫非就是最大公约数；最大公约数就是能同时为两整数

Question

谁能用通俗易懂的方法简述下什么是辗转相除法,我知道最小公约数和最大公倍数的原理.12,8；最大公约数是4,最小公倍数是24；那余数4莫非就是最大公约数；最大公约数就是能同时为两整数相除的大数；
PS：推荐我去网站看的免了,我理解不了,
p=n*m;
while(m!=0)
{r=n%m;n=m;m=r}
令 n=12.m=9；
执行过程如下
p=108；
m= =0 // 判断条件
r=12%9=3； //求余
n=9； // m的值赋给n
m=3； // r的值赋给m
m= =0 //while 循环
r=9%3=0；
n=3；
m=0；
m==0 // 循环停止
为什么非得到0为止才能求出最大公约数和最小公倍数~

Answer 1

这个叫欧几里得算法（通俗的说是辗转相除法）先说明下gcd(m,n)代表m,n的最大公约数,先设最大公约数为x根据这个算法gcd(m,n)=gcd(n,m%n)=.=gcd(x,0)=x这就是为什么一直要除到0为止最小公倍数就是m*n/x,这个是数学常识...