辗转相除法和更相减损术以及短除法都可以求最大公约数
1.辗转相除法
例：求80和36的最大公约数
80=36*2+8
36=8*4+4
8=4*2+0
所以最大公约数是42
算法：就是用小数除大数,如果余数不是零,就把余数和较小的数构成一组新数,继续上面的除法,知道大数被小数约尽,此时比较小的数就是最大公约数
2.更相减损术
还是上面的那个例子 可以用更相减损术计算
80-36=44
44-36=8
36-8=28
28-8=20
20-8=12
12-8=4
8-4=4
算法：用大数减去小数,将差和较小的数构成一对新数,再用大数减去小数 一直到差与较小数相等 此时差就是最大公约数
3.短除法