輾轉相除法

輾轉相除法是求最大公因數很有效率的方法. 首先我們介紹輾轉相除法的原理. Lemma 1.3.1 若a, b $ \in$ $ \mathbb {N}$ 且a = bh + r, 其中h, r $ \in$ $ \mathbb {Z}$ ... 下一頁:質數 上一頁:整數的基本性質 前一頁:除法原理 輾轉相除法 輾轉相除法是求最大公因數很有效率的方法. 首先我們介紹輾轉相除法的原理. Lemma1.3.1  若 a,b且a=bh+r,其中 h,r,則 gcd(a,b)=gcd(b,r). 証明. 假設 d1=gcd(a,b)且 d2=gcd(b,r).我們證明d1|d2且 d2|d1,因而可利用Proposition1.1.3(2)以及d1,d2 皆為正數得證d1=d2. 因d1|a且d1|b利用Corollary1.1.2我們知 d1|a-bh=r.因為d1|b,d1|r且 d2=gcd(b,r)故由 Proposition1.2.5知d1|d2.另一方面,因為d2|b且 d2|r故 d2|bh+r=a.因此可得d2|d1. Lemma1.3.1告訴我們當a>b>0時,要求a,b 的最大公因數我們可以先將a除以b所得餘數若為r,則a,b 的最大公因數等於b和r的最大公因數.因為 0rb.由除法原理我們知存在 h0,r0使得 a=bh0+r0,    其中 0r00,則存在 h1,r1使得 b=r0h1+r1,    其中 0r10,則存在 h2,r2使得 r0=r1h2+r2,    其中 0r2r1>r2>...是嚴格遞減的,因為 r0和0之間最多僅能插入r0-1個正整數,所以我們知道一定會有 nr0使得rn=0. 若r0=0,即a=bh0,故知b為a之因數,得證b為a,b 的最大公因數.若r0>0,則由Lemma1.3.1知 gcd(a,b)=gcd(b,r0)=gcd(r0,r1)=...=gcd(rn-1,rn)=gcd(rn-1,0)=rn-1. 現在我們來看用輾轉相除法求最大公因數的例子. Example1.3.3  我們求a=481和b=221的最大公因數.首先由除法原理得 481=2.221+39,知r0=39.因此再考慮b=221除以r0=39得 221=5.39+26,知r1=26.再以r0=39除以r1=26得 39=1.26+13,知r2=13.最後因為r2=13整除r1=26知 r3=0,故由Theorem1.3.2知 gcd(481,221)=r2=13. 在利用輾轉相除法求最大公因數時,大家不必真的求到rn=0. 例如在上例中可看出r0=39和r1=26的最大公因數是13,利用 Lemma1.3.1馬上得知 gcd(a,b)=13. 在上一節Corollary1.2.5告訴我們若 gcd(a,b)=d,則存在 m,n使得d=ma+nb.當時我們沒有提到如何找到此m,n. 現在我們利用輾轉相除法來介紹一個找到m,n的方法.我們沿用Theorem 1.3.2的符號.首先看r0=0的情形,此時 d=gcd(a,b)=b 所以若令m=0,n=1,則我們有d=b=ma+nb.當r00但 r1=0時,我們知 d=gcd(a,b)=r0.故利用 a=bh0+r0知,若令 m=1,n=-h0,則 d=r0=ma+nb.同理若r00,r10但 r2=0,則知 d=gcd(a,b)=r1.故利用 a=bh0+r0以及 b=r0h1+r1知 r1=b-r0h1=b-(a-bh0)h1=-h1a+(1+h0h1)b. 因此若令m=-h1且 n=1+h0h1,則 d=r1=ma+nb.依照此法,當 r0,r1和r2皆不為0時,由於 d=gcd(a,b)=rn-1故由 rn-3=rn-2hn-1+rn-1知 d=rn-3-hn-1rn-2. 利用前面推導方式我們知存在 m1,m2,n1,n2使得 rn-3=m1a+n1b且 rn-2=m2a+n2b故代入得 d=(m1a+n1b)-hn-1(m2a+n2b)=(m1-hn-1m2)a+(n1-hn-1n2)b. 因此若令 m=m1-hn-1m2且 n=n1-hn-1n2,則d=ma+nb. 上面的說明看似好像當r00時對每一個 i{0,1,...,n-2} 要先將ri寫成 ri=mia+nib,最後才可將d=rn-1寫成 ma+nb的形式.其實這只是論證時的方便,在實際操作時我們其實是將每個 ri寫成 mi'ri-2+ni'ri-1的形式慢慢逆推回d=ma+nb. 請看以下的例子. Example1.3.4  我們試著利用Example1.3.3所得結果找到 m,n使得 13=gcd(481,221)=481m+221n.首先我們有 13=r2=39-26=r0-r1.而 r1=221-5.39=b-5r0,故得 13=r0-(b-5r0)=6r0-b.再由 r0=481-2.221=a-2b,得知 13=6(a-2b)-b=6a-13b.故得m=6且 n=-13會滿足 13=481m+221n. 要注意這裡找到的m,n並不會是唯一滿足d=ma+nb的一組解. 雖然上面的推演過程好像會只有一組解, 不過只能說是用上面的方法會得到一組解,並不能擔保可找到所有的解. 比方說若令m'=m+b,n'=n-a,則 m'a+n'b=(m+b)a+(n-a)b=ma+nb=d. 所以m',n'也會是另一組解.所以以後當要探討唯一性時, 若沒有充分的理由千萬不能說由前面的推導過程看出是唯一的就斷言是唯一. 一般的作法是假設你有兩組解, 再利用這兩組解所共同滿足的式子找到兩者之間的關係. 我們看看以下的作法. Proposition1.3.5  假設 a,b且 d=gcd(a,b).若 x=m0,y=n0是d=ax+by 的一組整數解,則對任意 t, x=m0+bt/d,y=n0-at/d皆為 d=ax+by的一組整數解,而且d=ax+by的所有整數解必為 x=m0+bt/d,y=n0-at/d其中 t這樣的形式. 証明. 假設x=m,y=n是d=ax+by的一組解.由於已假設 x=m0,y=n0 也是一組解,故得 am+bn=am0+bn0.也就是說 a(m-m0)=b(n0-n). 由於 d=gcd(a,b),我們可以假設a=a'd,b=b'd其中 a',b' 且 gcd(a',b')=1(參見Corollary1.2.3).因此得 a'(m-m0)=b'(n0-n).利用 b'|a'(m-m0), gcd(a',b')=1以及 Proposition1.2.7(1)得b'|m-m0.也就是說存在 t 使得m-m0=b't.故知 m=m0+b't=m0+bt/d.將 m=m0+bt/d代回 am+bn=am0+bn0可得 n=n0-at/d,因此得證d=ax+by的整數解都是 x=m0+bt/d,y=n0-at/d其中 t這樣的形式. 最後我們僅要確認對任意 t, x=m0+bt/d,y=n0-at/d皆為 d=ax+by的一組整數解.然而將 x=m0+bt/d,y=n0-at/d代入ax+by 得 a(m0+bt/d)+b(n0-at/d)=am0+bn0=d,故得證本定理. 利用Proposition1.3.5我們就可利用Example1.3.4找到 13=481x+221y的一組整數解x=6,y=-13得到 x=6+17t,y=-13-37t 其中 t是 13=481x+221y所有的整數解. 下一頁:質數 上一頁:整數的基本性質 前一頁:除法原理 Li 2007-06-28