求36963与59570的最大公约数.

通过观察容易发现，36963有约数3×3。而59570没有质数3。59570有质因数2和5，而36963没有质因数2和5。所以可以从36963中分解出3×3，从59570中分解出2×5，再求其余部分的最大公约数。

36963=3×3×4107
59570=2×5×5957

辗转相除法
用大数除以小数再用上次运算中的除数除以余数，如此反复除，直到余数为零。最后一个除数就是两数的最大公约数。这是因为：两个数的最大公约数，同时是两个数的约数，也就是余数的约数。
5957/4107=1...1850
4107/1850=2...407
1850/407=4...222
407/222=1...185
222/185=1...37
185/37=5.....余数为0

∴（36963，59570）=37

用辗转相除法：
59570-36963=22607
36963-22607=14356
22607-14356=8251
14356-8251=6105
8251-6105=2146
6105-2*2146=1813
2146-1813=333
1813-5*333=148
333-2*148=37
148=4*37，所以最大公约数37。
36963/37=999
59570/37=1610

36963=3*3*3*37*37，质因数分解
59570可以对1个37整除，对3不能
所以两数的最大公约数是37

后者约数只能为1或2或5或10的倍数，与前者类比易知工约数只有1