尼考曼彻斯法的特色是做一系列减法,辗转相减,从而求得最大公约数.例如:两个自然数35和14,用大数减去小数,(35,14)->(21,14)->(7,14),此时,7小于14,要做一次交换,把14作为被减数,即(14,7)->(7,7),再做一次相减,结果为0,这样也就求出了最大公约数7.证明:设a=bq1+r1(0b=r1q2+r2(0r1=r2q3+r3(0......只要r1,r2,r3......不是0就可以继续写下去我们看到:b>r1>r2>r3>......>0b是有限的r1,r2,r3是整数所以至多b步后,必有rn=0rn-2=rn-1qn+rnrn-1=rn*qn+1+0由此可以得到(a,b)=rn.尼考曼彻斯法的特色是做一系列减法,辗转相减,从而求得最大公约数.例如:两个自然数35和14,用大数减去小数,(35,14)-(21,14)-(7,14),此时,7小于14,要做一次交换,把14作为被减数,即(14,7)-(7,7),再做一次相减,结果为0,这样也就求出了最大公约数7. 证明: 设 a=bq1+r1(0 b=r1q2+r2(0 r1=r2q3+r3(0  只要r1,r2,r3不是0就可以继续写下去 我们看到: br1r2r30 b是有限的r1,r2,r3是整数 所以至多b步后,必有rn=0 rn-2=rn-1qn+rn rn-1=rn*qn+1+0 由此可以得到(a,b)=rn