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

方法介绍

辗转相减法（求最大公约数），即尼考曼彻斯法，其特色是做一系列减法，从而求得最大公约数。例如 ：两个自然数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