令c=gcd（a,b），则设a=mc，b=nc，根据前提有r =a-kb=mc-knc=(m-kn)c
由上，可知c也是r的因数，故可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公因数成为cd，而非c】
所以 gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。
考虑用较大数除以较小数，求得商和余数：
8251=6105×1+2146
6105=2146×2+1813
2146=1813×1+333
1813=333×5+148
333=148×2+37
148=37×4
最后除数37是148和37的最大公因数，也就是8251与6105的最大公因数。
约数也叫做因数，是因数的另一个称呼。
更相减损术
更相减损术出自《
九章算术》的一种求
最大公约数的算法，它原本是为
约分而设计的，但它适用于任何需要求最大公约数的场合。其原文为：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言就是
第一步：任意给定两个正整数a、b；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的
减数和差相等为止。这个数就是a、b的最大公约数。
分析：由于63不是偶数，把98和63以大数减小数，并辗转相减：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以，98和63的最大公约数为7。
注：以上首三个方法同样适用于求多个自然数的最大公约数
求约公式
n=p⑴^α⑴·p⑵^α*⑵·…·p(k)^α（k）
其中p⑴、p⑵、…p（k）是不同的质数，α⑴、α⑵、…α（k）
是正整数，则形如
n=p⑴^β⑴·p⑵^β*⑵·…·p(k)^β（k）
的数都是n的约数，其中β⑴可取a⑴+1个值：0,1,2，…，α⑴；β⑵可取α⑵+1个值：0,1,2，…，α⑵…；β（k）可取a(k)+1个值：0,1,2，…，α（k）.且n的约数也都是上述形式，根据乘法原理，n的约数共有
（α⑴+1）（α⑵+1）…（α（k）+1） ⑺
个。
式⑺即为求一个数约数个数的公式。
负约数
定义
国内课本中，最先提到约数这个概念是在小学，而此时还没学负数。
等到学了负数，一般要直到大学数学系“
初等数论”中才严格定义约数，那个时候就包括负约数了。
如果d|a并且d≥0，则我们说d是a的约数。注意，d|a当且仅当（-d)|a，因此定义约数为
非负整数不会失去一般性，只要明白a的任何约数的相应负数同样能整除a。一个整数a的正约数最小为1，最大为|a|。
例题
105的负约数的和是多少？
105的所有负约数就是105的所有
正约数的相反数所组成的集合。
105的正约数有1,3,5,7,15,21,35,105
105的负约数有-1,-3,-5,-7,-15,-21,-35,-105
其和为 -（1+3+5+7+15+21+35+105） = ﹣192