2007年7月20日 星期五

大衍求一術


(這個是中國潛望鏡原型,跟大衍求一術沒關係)


先簡介一下同餘算式:
a≡b(mod c)意思就是(a-b)可被c整除,其中a,b,c都是整數。或者用更口語化的說法,a和b去除c的餘數相同。我們稱此算式為『a和b對模C同餘』。這裡就是一個意譯加上音譯的例子,模c是 mod c 的音譯,同餘是意譯。

那麼大衍求一術是在幹麼?它就是一套方法,可以迅速的解:
ka≡1(mod c),其中a,c互質且已知,k=?
這個問題。根據數論,k必定有解,所以不怕解不出來。

具體作法如下:如果a>c,那麼令c除a所得之餘數為a1。用a1取代a可得k(a1)≡1(mod c),這個問題與原問題等價。將a1放在右上,c放在右下,1放在左上,0放在左下。將右上之數除右下之數,所得餘數代換被除之數,並將所得商數乘上除數左邊之數,加上被除數左邊之數後取代被除數左邊之數。按此方法一直進行右排中的小數除右排中的大數,以餘數代換大數,以商數乘除數左邊之數後加入被除數左邊之數,直到右上方為1為止,此時左上方的值為k。有一點要注意的是以1為除數的話,都令其餘數為1。

範例:
k*77≡1(mod 9)
等同於
k*5≡1(mod 9),因為77≡5(mod 9)

步驟一:
1 5
0 9

步驟二:
1 5
1 4

步驟三:
2 1
1 4

因此k=2。