如何用更相减损术求最大公约数?

给定任意的两个正整数，例如40，30

40和30都是偶数，所以要用2给它们约简。当然如果两个数都是奇数，或者一奇数一偶数的情况这个步骤不用做。

以较大的减去较小的，20比15大，所以20减15，等于5。

看看所得的差和刚才较小的那个数也就是减数是否相等，如果不相等就比较一下所得的差和减数哪个大，用大的数减去小的。15和5不相等，所以15减5，等于10。

减数和差又不相等，重复上一步操作。用10减5，等于5。

这下你会发现减数和所得的差相等了，都是5，那么5就是40和30的最小公约数了。