辗转相减法是一种简便的求出两数最大公约数的方法。(更相减损术)

　　辗转相减法(求最大公约数)，即尼考曼彻斯法，其特色是做一系列减法，从而求得最大公约数。例如 :两个自然数35和14，用大数减去小数，(35,14)->(21,14)->(7,14)，此时，7小于14，要做一次交换，把14作为被减数，即(14,7)->(7,7)，再做一次相减，结果为0，这样也就求出了最大公约数7

　　证明:

　　设

　　a=bq1+r1(0<r1<b)

　　b=r1q2+r2(0<r2<r1)

　　r1=r2q3+r3(0<r3<r2)

　　……

　　只要r1,r2,r3……不是0就可以继续写下去

　　我们看到:

　　b>r1>r2>r3>……>0

　　b是有限的r1,r2,r3是整数

　　所以至多b步后，必有rn=0

　　rn-2=rn-1qn + rn

　　rn-1 = rn*qn+1+0

　　由此可以得到(a,b)=rn

　　证明II:

　　在介绍这个方法之前，先说明整除性的一些特点(下文的所有数都是正整数，不再重覆)，我们可以这样给出整除性的定义:

　　对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。

　　如果a能被c整除，并且b也能被c整除，则c为a、b的公因数(公有因数)。

　　由此我们可以得出以下推论:

　　推论1、如果a能被b整除(a=qb)，若k为正整数，则ka也能被b整除(ka=kqb)

　　推论2、如果a能被c整除(a=hc)，b也能被c整除(b=tc)，则(a±b)也能被c整除

　　因为:将二式相加:a+b=hc+tc=(h+t)c 同理二式相减:a-b=hc-tc=(h-t)c

　　所以:(a±b)也能被c整除

　　推论3、如果a能被b整除(a=qb)，b也能被a整除(b=ta)，则a=b

　　因为:a=qb b=ta a=qta qt=1 因为q、t均为正整数，所以t=q=1

　　所以:a=b

　　辗转相除法是用来计算两个数的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。其理论如下:

　　如果 q 和 r 是 m 除以 n 的商及余数，即 m=nq+r，则 gcd(m,n)=gcd(n,r)。

　　证明是这样的: 设 a=gcd(m,n)，b=gcd(n,r)

　　a=gcd(m,n)

　　m能被a整除，并且n也能被a整除，则由推论1得:qn也能被a整除

　　由推论2得:m-qn也能被a整除

　　而m-qn=r，即r也能被a整除，

　　因为b是最大公约数(最大公约数定义)，所以b能被a整除

　　同时

　　b=gcd(n,r)

　　n能被b整除，并且r也能被b整除，则由推论1得:qn也能被b整除

　　由推论2得:qn+r也能被b整除

　　而m=qn+r，即m也能被b整除

　　因为a是最大公约数，所以a能被b整除。

　　由推论3，得到，a=b

　　例如计算 gcd(546, 429)

　　gcd(546, 429) 546=1*429+117

　　=gcd(429, 117) 429=3*117+78

　　=gcd(117, 78) 117=1*78+39

　　=gcd(78, 39) 78=2*39

　　=39