利用辗转相除法求3869与6497的最大公约数与最小公倍数

利用辗转相除法求3869与6497的最大公约数与最小公倍数

6497=1×3869+2628
3869=1×2628+1241
2628=1×1241+146
1241=8×146+73
146=2×73
∴3869与6497的最大公约数为73．
最小公倍数53×73×89=344341．

6497=3869×1+2628， 
3869=2628×1+1241， 

2628=1241×2+146， 
1241=146×8+73， 
146=73×2+0，

∴3869与6497的最大公约数为73， 
最小公倍数为3869×6497÷73=344341。


辗转相除的定义：
所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。
辗转相除法的一个程序算法的步骤：
第一步：输入两个正整数m,n(m>n).
第二步：计算m除以n所得的余数r.
第三步：m=n,n=r.
第四步：若r＝0,则m,n的最大公约数等于m；否则转到第二步.第五步：输出最大公约数m.

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息！