尼考曼徹斯法

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

基本介紹