輾轉相減法是一種簡便的求出兩數最大公約數的方法。（更相減損術）
正文
輾轉相減法（求最大公約數），即尼考曼徹斯法，其特色是做一系列減法，從而求得最大公約數。例如 ：兩個自然數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
輾轉相減法是一種簡便的求出兩數最大公約數的方法。（更相減損術）
正文
輾轉相減法（求最大公約數），即尼考曼徹斯法，其特色是做一系列減法，從而求得最大公約數。例如 ：兩個自然數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