韩信点兵

韩信点兵 誰來點兵 摘要: 本研究從課本題目加以探討,從代數學中「餘數定理」取出韓信點兵這個有趣且深奧的問題,提出來討論。在實驗當中以「疊代法」著手進行,由兩個餘數問題推廣到三個餘數問題,甚至到更多個餘數問題,以找出其規律和法則。 壹、研究動機: 「兵不知數,三三數之剩二,五五數之剩三,七七數之剩二」。這在古代成為人人討論之話題,看過許多韓信點兵有關的資料以後,更加想了解箇中之道理,而那股動力是看到中國古代「孫子算經」中所提出的「物不知數」也就是課本中之『韓信點兵』亦稱之『中國剩餘定理』,尤其中國早期已發現其解法,比西方更早,此也成為近代抽象代數中有名之定理。 貳、研究目的: 一、探討「餘數不同,不足數亦不同」之問題。 二、探討「除數不同」,可否得到「疊代次數」。 三、探討「二個餘數問題至多個餘數問題」。 四、找出是否有通解可直接解題。 參、研究設備及器材: 電腦應用軟體(Excel、Word),紙,筆。 肆、研究過程或方法 首先我們先介紹一下什麼是高斯符號,因為在實驗步驟中會運用到 BB，，所謂的高斯符號代不大於的最大整數 ,,AA，， 9613，，，，，，例如: ,, ,4,2,3,,,,,,522，，，，，， 我們先從幾個簡單的例子來看 一、 某數除以3餘2,除以7餘3的最小正整數解為何, 根據題目我們可以把某數假設為3x，2,7y，3 7y，16y，y，1y，1x,,,2y， 經過整理後可以表示成 333 y，1t, 令y,3t,1所以 3 xx,2y，t,2(3t,1)，t,7t,2 那麼原本就可以表示成 x,7t,2 因此我們便得到一組通解 y,3t,1 x,5 t,1 所以當 時,得到 帶入原式 3x，2,7y，3 y,2 17，21D 即可求出最小正整數解為17 而通解為 其中為0或正整數 D , 由上面例子可以發現疊代的次數可由輾轉相除法先算出 3 7 2 6 1 (1) 將3和7作輾轉相除法,做到餘數為1止,發現ㄧ次後即得到,故此題只 需要疊代一次 (2) 發現餘數為整理後未知數的係數 二、 某數除以5餘3,除以13餘7的最小正整數解為何, 經過第一題的例子,我們可以先行推算出要疊代幾次後才可求出最小整數解 1 5 13 2 3 10 2 3 1 2 1 (1) 將5和13作輾轉相除法,做三遍後即得到餘數為1,則此題只需要疊代三次 (2) 發現疊代三次其整理後餘數即為未知數的係數 根據題目我們可以把某數假設為 5x，3,13y，7 13y，410y，3y，43y，4x,,,2y， 經過整理後可以表示成 555 3y，45t,4t,y, 令所以 53 5432421tttt,，,,yt,,,,，1 經過整理後 333 21t,31211zzzz，，，，z,tz,,,， 令,得到 3222 z，1zw,,21w, 令,得到 2 那麼原本就可以表示成 x xyttzttzzwzwww,，,,，，,，,,，，,,,，,,,22(1)3223()225(21)32137 ytzzwwww,,，,，,,,，,,,1212(21)153 xw,,137 因此我們便得到一組通解 yw,,53 x,6 w,1 所以當 時,得到 帶入原式 5x，3,13y，7 y,2 33，65D 即可求出最小正整數解為33 而通解為 其中為0或正整數 D 三、 某數除以3餘2,除以11餘1的最小正整數解為何, 我們可以先行推算出要疊代幾次後才可求出最小整數解 1 3 11 3 2 9 1 2 (1) 將3和11作輾轉相除法,做二遍後即得到餘數為1,則此題只需要疊代二次 (2) 發現疊代二次其整理後餘數即為未知數的係數 根據題目我們可以把某數假設為 3x，2,11y，1 11y,19y，2y,12y,1x,,,3y，經過整理後可以表示成 333 2y,13t，1t,y,令所以 32 3t，12t，t，1t，1y,,,t，經過整理後 222 t，1t,2z,1z,令,得到 2 那麼原本x就可以表示 x,3y，t,3(2z,1，z)，(2z,1),9z,3，2z,1,11z,4 y,t，z,2z,1，z,3z,1 x,11z,4 因此我們便得到一組通解 y,3z,1 x,7 z,13x，2,11y，1所以當 時,得到 帶入原式 y,2 23，33D即可求出最小正整數解為23 而通解為 其中為0或正整數 D , 根據上述例題我們已經熟悉了疊代方法,並且可以預知需疊代幾次後才可以正 確求出最小正整數解,現在就要用疊代方法來求出韓信的兵力「兵不知數,三 三數之剩二,五五數之剩三,七七數之剩二」最少有幾人,所以我們可以先算 出某數除以3餘2,除以5餘3的最小正整數解,再求跟除以7餘2的最小正 整數解即可 某數除以3餘2,除以5餘3的最小正整數解為何, 我們可以先行推算出要疊代幾次後才可求出最小整數解 1 3 5 1 2 3 1 2 (1) 將3和5作輾轉相除法,做二遍後即得到餘數為1,則此題只需要疊代二次 (2) 發現疊代二次其整理後餘數即為未知數的係數 根據題目我們可以把某數假設為 3x，2,5y，3 5y，13y，2y,12y，1x,,,y，經過整理後可以表示成 333 3t,12y，1y,t,令所以 32 3t,12t，t,1t,1y,,,t，經過整理後 222 t,1t,2z，1z,令,得到 2 那麼原本就可以表示 xx,y，t,t，z，t,2t，z,5z，2 y,t，z,2z，1，z,3z，1 x,5z，2 因此我們便得到一組通解 y,3z，1 x,2 z,0所以當 時,得到 帶入原式3x，2,5y，3 y,1 8，15DD即可求出最小正整數解為8 而通解為 其中為0或正整數 再求某數除以7餘2,除以15餘8的最小正整數解為何, 我們可以先行推算出要疊代幾次後才可求出最小整數解 7 15 2 14 1 (1) 將7和15作輾轉相除法,做一遍後即得到餘數為1,則此題只需要疊代一次 (2) 發現疊代一次其整理後餘數即為未知數的係數 根據題目我們可以把某數假設為 7x，2,15y，8 15y，614y，y，6y，6x,,,2y，經過整理後可以表示成 777 y，6令所以 t,y,7t,67 經過整理後 y,7t,6 那麼原本就可以表示 xx,2y，t,15t,12 x,15t,12 因此我們便得到一組通解 y,7t,6 x,3 t,1所以當 時,得到 帶入原式 7x，2,15y，8 y,1 23，105DD即可求出最小正整數解為823而通解為 其中為0或正整數 所以我們可以得知韓信最少的兵力為23人 現在我們嘗試著把這種式子的通式解找出來所以假設: 某數除以A餘a,除以B餘b的最小正整數解為何, A,B為了方便起見,我們假設，， A,B,1 根據題目所以我們可以把某數假設為 Ax，a,By，b 經過整理後可以表示成 ,,B，，BB，，，，,B,A,y，(b,a)By，Ay,Ay，(b,a),,,,,,,,ABy，(b,a)BAA，，，，，，，，,, x,,,y，,,AAAA，， ,,B，，,B,A,y，(b,a),,,,AAt,(b,a)，，,,令 所以 t,y,A,,B，，,B,A,,,,,A，，,,case1: ,,B，，當時,我們就不需要繼續假設參數 ,B,A,,1,,,,A，，,, B，，那麼原本就可以表示成 xy,At,(b,a)x,y，t,,A，， B，， x,y，t,,A，，因此我們便得到一組通解 y,At,(b,a) B，，為整數,而且滿足 而且 y,At,(b,a),0ttx,y，t,0,,A，， B，， x,y，t,,A，，所以當滿足上述條件時時,得到 t y,At,(b,a) 帶入原式 Ax，a,By，b ,,B，，即可求出最小正整數解為 A,y，t,，a,,,,A，，,, ,,B，，D而通解為 其中為0或正整數 AytaABD，，，,,,,,,,A，，,, case2: ,,B，，當,B,A,,1時,我們就需要繼續假設參數 ,,,,A，，,, ，，，， ,,,,ABAB,,,,，，，，,,,,AtBAtBAtba，,,,,,(),,,,,,,,AA,,,,BB,,,,，，，，，，，，,,,,BABA,,,,,,,,,,,,,,AA，，，，,,,,，，，，經過整理後 y,,,B，，BA,,,,,A，，,, ,,，，,,,,,,,,AB，，,,A,,B,A,t,(b,a),,,,,,,,A,,B，，，，，，,,,,,B,A,,,,,,,,,,,A，，,,A，，,,,, ,t，,,,,,,BB，，，，,B,A,,B,A,,,,,,,,,,,AA，，，，,,,,，， ,,，，,,,,,,,,AB，，,,A,,B,A,t,(b,a),,,,,,,,A,,B，，，，,,,,,B,A,,,,,,,,,A，，,,，，,,Z,令, B，，B,A,,A，， ,,B，，,B,A,Z，(b,a),,,,A，，,,t,得到 ,,，，,,,,,,,,AB，，,,A,,B,A,,,,,,,,,A,,B，，，，,,,,,B,A,,,,,,,,,A，，,,，，,,subcase1: ,,，，,,,,,,,,AB，，,,當時,就不需繼續假設參數 A,,B,A,,1,,,,,,,,A,,B，，，，,,,,,B,A,,,,,,,,,A，，,,，，,,那麼原本x就可以表示成 BBB,,，，，，，，xytyBAzba,，,，,，,() ,,,,,,,,AAA，，，，，，,, ，， ,,,,,,AB，，,,,,y,,B,A,z，(b,a)，z ,,,,,,,,A,,B，，，，,,,,,B,A,,,,,,,A，，,,，， 因此我們便得到一組通解 BB,,，，，， xyBAzba,，,，,(),,,,,,AA，，，，,, ，， ,,,,,,AB，，,,,,y,,B,A,z，(b,a)，z ,,,,,,,,A,,B，，，，,,,,,B,A,,,,,,,A，，,,，， x,0為整數,而且滿足 而且 所以當滿足上述條件時時,得到 y,0zzz BB,,，，，， xyBAzba,，,，,(),,,,,,AA，，，，,, ，， ,,,,,,AB，，,,,,y,,B,A,z，(b,a)，z 帶入原式 Ax，a,By，b,,,,,,,,A,,B，，，，,,,,,B,A,,,,,,,A，，,,，， 即可求出最小正整數解為 ,,,,，，,,,,,,,,,,,,,,,,BABB，，，，，，,,,, A,B,A,z，(b,a)，z，,B,A,z，(b,a)，a,,,,,,,,,,,,,,,,,,AAA,,B，，，，，，，，,,,,,,,,,,,B,A,,,,,,,,,,,A，，,,，，,,,, 而通解為 ,,,,，，,,,,,,,,BABB,,,,，，，，，，,,,,,, 其ABAzbazBAzbaaABD,，,，，,，,，，()(),,,,,,,,,,,,,,,,,,,,,AAA,,B，，，，，，，，,,,,,,BA,,,,,,,,,,,,,A，，,,，，,,,, D中為0或正整數 subcase2: ,,，，,,,,,,,,AB，，,,當時,就需繼續假設參數 A,,B,A,,1,,,,,,,,A,,B，，，，,,,,,B,A,,,,,,,,,A，，,,，，,, 而轉換的過程就跟上面的步驟一樣,所以就不再敘述 伍、研究結果 一、任意兩個互質的數,同時除某數,雖無法確定某數,但如果利用上式的通式卻可以 容易的找出最小整數解與所有可能的數。 二、疊代法的次數與兩數使用輾轉相除法的次數完全一樣。 三、若有三個或三個以上互值的數,只要兩兩先照上述方法操作也能找出一般式的通解。 陸、討論 一、觀察上述的操作方法,所疊代出來的參數不是0就是1,參數的值是否能由疊代的 次數與兩者餘數關係決定,是否有一定的規律, 柒、結論 一、任意兩個互質的數,同時除某數,雖無法確定某數,但如果利用上式的通式卻可以 容易的找出最小整數解與所有可能的數。 二、疊代法的次數與兩數使用輾轉相除法的次數完全一樣。 三、若有三個或三個以上互值的數,只要兩兩先照上述方法操作也能找出一般式的通解。 捌、參考資料及其他