概念解读
辗转相除法和更相减损术
我国古代数学发展曾经处于世界领先水平，特别是宋、元时期的“算法”，其中可以同欧几里德辗转相除法相媲美的是可以求两个数字的最大公约数的更相减损术。
辗转相除法
用大数除以小数，得到商和余数，再用上面的除数除以余数，又得到新的余数，继续做下去，直到刚好能够整除为止，得到两个数的最大公约数．
辗转相除法解读：
给定两个正整数 36 48
用大数除以小数，得到商和余数， 48÷36=1…12
再用上面的除数除以余数，又得到新的余数，
继续做下去，直到刚好能够整除为止， 36÷12=3
最后的除数就是两个数的最大公约数． 12
即为原两数的最大公约数 36和48的最大公约数是12
用“辗转相除法”求得459和357的最大公约数是
解：
∵459÷357=1…102，357÷102=3…51，102÷51=2，∴459和357的最大公约数是51
2183和1947的最大公约数是
解：∵2183÷1947=1…236，1947÷236=8…59，236÷59=4，∴2183和1947的最大公约数是：59
数4557，1953，5115的最大公约数为（　　）
先求出其中二个数4557，1953；4557，5115的最大公约数，之后我们易求出三个数4557，1953，5115的最大公约数．
解：4557=1953×2+6511953=651×3∴4557，1953的最大公约数是651；5115=4557×1+5584557=558×8+93558=93×6，故4557，5115的最大公约数为93，由于651=93×7三个数4557，1953，5115的最大公约数93．
更相减损术
给定两个正整数，判断它们是否都是偶数，若是，先用2约简，直到两者不都是偶数，用大数减小数，减数和差构成一对新数，再用大数减小数，直到两者相等为止，此时相等的数乘约简的数，即为原两数的最大公约数。
更相减损术解读：
给定两个正整数 36 48
判断它们是否都是偶数 是
若是，先用2约简 18 24 ÷2
判断它们是否都是偶数 是
若是，先用2约简 9 12 ÷2
判断它们是否都是偶数 不是
大数减小数 12-9=3
减数和差构成一对新数，再大减小 9-3=6
减数和差构成一对新数，再大减小 6-3=3
直到两者相等为止，此时相等的数是 3
相等的数乘约简的数 3*2*2=12
即为原两数的最大公约数 36和48的最大公约数是12
更相减损术解读：
给定两个正整数 36 48

判断它们是否都是偶数 是
若是，先用2约简 18 24 ÷2
判断它们是否都是偶数 是
若是，先用2约简 9 12 ÷2
判断它们是否都是偶数 不是

大数减小数 12-9=3
减数和差构成一对新数，再大减小 9-3=6
减数和差构成一对新数，再大减小 6-3=3
直到两者相等为止，此时相等的数是 3
相等的数乘约简的数 3*2*2=12
即为原两数的最大公约数 36和48的最大公约数是12
更相减损术程序解读：
INPUT “m,n=”;m,n 36 48
i=0
WHILE m MOD 2=0 AND n MOD 2=0 是
m=m/2
n=n/2
i=i+1 18 24 ÷2 (i计数1次)
WHILE m MOD 2=0 AND n MOD 2=0 是
m=m/2
n=n/2
i=i+1 9 12 ÷2 (i计数1次)
WHILE m MOD 2=0 AND n MOD 2=0 不是
WEND
DO
IF m＜n THEN
r=m
m=n
n=r
END IF
m=m-n 把差的值给m，保留n
LOOP UNTIL m=0
n=n*2^I
PRINT “最大公约数为”; n
END
互换位置，保证m最大