大衍求一术与二元一次不定方程

《大衍求一术与二元一次不定方程》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、大衍求一術與二元一次不定方程文耀光摘要:「大衍求一術」是中國古代數學家秦九韶用以解一次同餘式組的方法。本文旨在介紹何謂大衍求一術,以及如何將之轉化為一遞歸求解形式(recursivemethodofsolution),並應用此法求解二元一次不定方程。I.引言非負整數,所以輾轉相除有限步之後,一定會產生以下的結果:給定兩個自然數a和b,要求取它們的GCD(a,b)=GCD(r,a)=···最大公因數GCD(a,b)有好幾種方法。現時=GCD(0,c)=c。香港小學數學課程裡討論的「列舉法」、「質因數分解法」和「短除法」都是常用的方法。

2、不例1:求299與247的最大公因數。過當a和b的數值很大時,使用「輾轉相解:除法」(EuclideanAlgorithm)會比較方便12992474和快捷。此法早在古希臘時代已經被發現,並247208且收錄在歐幾里德(Euclid)的名著「幾何原152393本」(約公元前300年)之中,其原理如下:3939定理1:設a、b是自然數,且a≤b。13若b=aq+r,其中0≤r

3、用39除52,得商數1及餘數13)用除法,可以求取任意兩個自然數的最大公(用13除39,得商數3及餘數0)因數。由於每次所產生的被除數a及除數r,都比原來的被除數b及除數a為小,且r為∴GCD(247,299)=GCD(52,247)86大衍求一術與二元一次不定方程87=GCD(39,52)=52−39=GCD(13,39)=52−(247−4×52)=GCD(0,13)=5×52−247=13。=5×(299−247)−247=5×299−6×247輾轉相除法除了可以用來求最大公因數之外,還可以用來解不定方程。它的原理是基由此求得

4、299x+247y=13的一個特殊整於以下的結果:數解為x0=5,y0=−6。設k為任意整數,那麼:定理2:設a、b為自然數。247k299k299(x0+)+247(y0−)=13,若d=GCD(a,b),那麼不定方程1313ax+by=d有整數解。所以299x+247y=13的一般整數解為:x=5+19k,y=−6−23k,推論1:設a、b為自然數。若GCD(a,b)=1,那麼不定方程其中k為任意整數。ax+by=1有整數解。這種解不定方程ax+by=GCD(a,b)的方法,稱為ExtendedEuclideanAlgo-定理3

5、:設a、b、c為自然數。rithm(參考Biggs(1990),Niven(1991)或不定方程ax+by=d有整數解當且Geddes(1992))。此法雖然簡單易明,可是僅當GCD(a,b)

6、d。在「倒推」的過程中需要不斷整理被除數和有關這些定理的證明,可以參考潘承彪除數的係數,實在是一件相當繁複而且容易(1998),此處從略。出錯的工作。那麼,是否可以改良一下呢?讓例2:求不定方程299x+247y=13我們在下一節為大家介紹。的一般整數解。II.大衍求一術解:根據例1的算式,將有餘數產生的每一步用橫式表示,可得:中國人在求解一

7、次同餘式組方面的歷史是十分悠久的,而且成就卓越。大約在公元299=247+52280至420年間出版的「孫子算經」之中,記247=4×52+39載有一道聞名的一次同餘式問題(簡稱「孫子52=39+13問題」)及其答案如下:『今有物不知其數,三三數之剩二,五五把以上數式逐步倒推而上,可得:數之剩三,七七數之剩二,問物幾何?』答曰:GCD(299,247)=13『二十三』。88數學傳播23卷3期民88年9月如果用現代的符號表示,「孫子問題」可使其滿足同餘式組(2)。由於此題所牽涉的以記作以下的一次同餘式組:數字比較小,利用「試誤法」或「

8、大衍求一術」(見以下敘述),可以得出α=2,β=1,x≡2(mod3)γ=1,因此「孫子問題」的解是:x≡3(mod5)(1)x≡2(mod7)x≡70×2+63×1+30×1≡23(mod105)。「孫子問題」之解法,可以推廣成為以下如果要解同餘式組(1),先要解出一組的中國剩餘定理(ChineseRemainderThe-正整數α、β、γ,使其滿足以下的同餘式組orem):(2):35α≡1(mod3)定理3:(中國剩餘定理)設m,m,1221β≡1(mod5)(2)...,mk是兩兩互質的自然數

9、,且M=15γ≡1(mod7)m1×m2×···×mk。如果存在整數αi(i=為什麼呢?因為如果α、β、γ存在的話,1,2,...,k)使得那麼根據同餘式組(2)可得:Mα≡1(modm)m111M35