尼考曼徹斯法

尼考曼徹斯法的特色是做一系列減法,輾轉相減,從而求得最大公約數。

基本介紹

  • 中文名:尼考曼徹斯法
  • 用途:求多個數的最大公約數
尼考曼徹斯法的特色是做一系列減法,輾轉相減,從而求得最大公約數。例如 :兩個自然數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

相關詞條

熱門詞條

聯絡我們