我们离结果越来越近!设a''''=185且b''''=37,相除 -  - 185里正好有五个37.因此gcd(185,37)=37.我们完成了计算:
185=5×37+0.
gcd(10693,2220) =gcd(2220,1813)
=gcd(1813,407)
=gcd(407,185)
=gcd(185,37)=37
我们找到了10693和2220的最大公约数,只用了五次除法!欧几里得的最大公约数算法可以总结如下:
在第6章中我们介绍了整数互素的概念.它可以这样描述:假设gcd(a
,b
)=1那么a
和b
互素.由于欧几里得算法可以高效地计算两个数字的gcd,它提供了一个有效的方法来查看两个数字是否互素.
欧几里