輾轉相減

b=r1q2+r2(0>r2>r1) rn rn

輾轉相減法（求最大公約數），既尼考曼徹斯法，其特色是做一系列減法，從而求得最大公約數。例如 ：兩個自然數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