1813＝333×5＋148

　　333＝148×2＋37

　　148＝37×4＋0

　　则37为8251与6105的最大公约数．

　　以上我们求最大公约数的方法就是辗转相除法．也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的．利用辗转相除法求最大公约数的步骤如下：

　　第一步：用较大的数除以较小的数得到一个商和一个余数；

　　第二步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数；

　　第三步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数；

　　依次计算直至，此时所得到的即为所求的最大公约数．

　　练习：利用辗转相除法求两数4081与20723的最大公约数

　　解：

　　2.更相减损术

　　我国早期也有解决求最大公约数问题的算法，就是更相减损术．

更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母之数，以少减多，更相减损，求其等也，以等数约之．