展開全部

你好。

【韓信暗點兵】歌訣：

三人同行七十夕，五數梅花二十一，七子團圓正半月，去百零五便得知。

韓信暗點兵，韓信不是一、二、三、點數，而是，讓隊伍列隊：

首先三人一列，記住多餘的人數；

再讓五人一列，記住多餘的人數；

再做七人一列，記住多餘的人數。

將上面三次多餘的人數相加。他就知道一共有多少人。

計算：

三列隊的餘數，比如說，餘數是二。則：2*70=140 （餘數不可能多餘二）

五佇列的餘數，比如說，餘數是四，則：4*21=84 （餘數不可能多餘四）

七佇列的餘數，比如說，餘數是六，則：6*15=90 （餘數不可能多餘六）

上列結果相加：140+84+90=314

假如說，一估計，沒有300多人，就：314—105=209

假如一看，還沒有200多人，再減去105，則：209——105=104

好。就是104人。

注：這裡面除了上面的計算以外，還要估算一下。大約數再進行比較計算。

物不知數

韓信點兵問題最早出自《孫子算經》。《孫子算經》是中國古代非常重要的數學著作，因數學家 孫子 貢獻最大而得名（關於孫子的資料不可考），大約成書於東晉十六國時期，現存最早為北宋刻本，全書分三卷：《捲上》、《卷中》、《卷下》，主要講述 度量規定 和 算籌運算 以及基於 它們的 數學應為問題，韓信點兵為 《卷下》第二十六題 ”物不知數“，原文如下：

今有物，不知其數。三、三數之，剩二；五、五數之，剩三；七、七數之，剩二。問物幾何？

答曰：二十三。

術曰：“三、三數之，剩二”，置一百四十；“五、五數之，剩三”，置六十三；“七、七數之，剩二”，置三十。並之，得二百三十三。以二百一十減之，即得。凡三、三數之，剩一，則置七十；五，五數之，剩一，則置二十一；七、七數之，剩一，則置十五。一百六以上，以一百五減之，即得。

題目翻譯成現今的數學語言如下：

有一個正整數 x，知 x 除以 3 餘 2、除以 5 餘數 3、除以 7 餘數 2， 求 x 的最小值。

這等價於求解《初等數論》中的 一次同餘方程組：

《孫子算經》給出的解法如下：

尋中最小正整數 x₁ ， 滿足： x₁ 被 5 和 7 整除 並且 除以 3 餘 1，即，5|x₁, 7|x₁ 並且 x₁ mod 3 = 1 ②

x₁ 被 5 和 7 整除，就意味著 被 5×7 = 35 整除，即， 35 | x₁，於是，令 x₁ = 35n（n ≥ 1）：

當 n = 1 時 x₁ = 35，35 mod 3 = 2 不滿足 ② 捨棄；

當 n = 2 時 x₁ = 70，70 mod 3 = 1 剛好滿足 ②，Bingo~~~。

由於 x₁ ≡ 1 (mod 3)，故 2x₁ ≡ 2 (mod 3)，於是 得到 2x₁ = 140，它滿足：除以 3 餘 2 並且 被 5 和 7 整除。

同理，

求得滿足：可被 3 和 7 整除 並且 除以 5 餘 1 的最小正整數 x₂ = 21，從而得到，同樣可被 3 和 7 整除 但 除以 5 餘 3 的 3x₂ = 63；

求得滿足：可被 3 和 5 整除 並且 除以 7 餘 1 的最小正整數 x₃ = 15，從而得到，同樣可被 3 和 5 整除 但 除以 7 餘 2 的 2x₃ = 30；

將上面的 結果 相加 得到： x’ = 2x₁ + 3x₂ + 2x₃ = 140 + 63 + 30 = 233，則 容易驗證 x‘ 是 同餘方程組 (1) 的一個解 ，但是 x’ 不是 最小整數解 x。很容易可以發現 x" 減去 一個 同時 被 3、5 和 7 整除 並且 不大於 x" 的 整數，結果依然 是 (1) 的解，由於，同時 3、5 和 7 整除，就 意味著 被 3×5×7 = 105 整除，於是得出：

x = x" (mod 105)

進而，有如下演算法：

令 x = x"；

如果 x > 105（原文為 106 = x₁ + x₂ + x₃ ） 則 令 x = x - 105，否則 x 為 最終答案；

具體過程如下：

x = x" = 233

[x = 233 > 105]： x = x - 105 = 233 - 105 = 128

[x = 128 > 105]： x = x - 105 = 128 - 105 = 23

[ x = 23 < 105]：OK！

這樣就得到了最終答案：x = 23。

將整個求解過程寫成算式就是：

x = 2×70 + 3×21 + 2×15 - 2×(3×5×7) = 23

為了方便記憶，發明 珠算 和 捲尺 的明朝數學家 程大位，在其所著的 《演算法統宗》 中，將 《孫子算經》的演算法編成 "孫子歌訣" 如下：

三人同行七十稀，

五樹梅花廿一枝，

七子團圓正半月，

除百零五便得知。

注：正半月就是十五天，除是除去（減去）之意。

韓信點兵

韓信點兵 泛指 ”物不知數“ 此類 一次同餘方程組 求解問題。南宋著名數學家 秦九韶 對 《孫子算經》中的演算法 進行了深入研究，將其擴充套件為『大衍總數術』，徹底解決了 韓信點兵問題，這就是 《初等數論》中的 中國剩餘定理（也稱 孫子定理）：

設 m₁, m₂, ..., m_n 是 兩兩互素 的 正整數，那麼對於任意整數 a₁, a₂, ..., a_n 組成的 一次同餘方程組：

在同餘意義下，必有唯一解：

其中：

驗證：易知，

再結合 (3"")，由 (3") 可以推出：

這就說明 (3") 的確 是 (3) 的解。

注：這裡只是給出了定理的驗證，並沒有嚴格證明 同餘意義下的唯一性。證明 中國剩餘定理，有多種方法大家有興趣可以參考《初等數論》。

秦九韶 分別稱 M、Mᵢ 、 Mᵢ⁻¹ 為 衍母、衍數、乘率，這裡的關鍵是求 乘率 Mᵢ⁻¹ ，方法如下：

令， r 是 Mᵢ 除以 mᵢ 的餘數，即，

於是：

進而：

然後，讓 mᵢ 和 r 輾轉相除，得到：

到 r_k = 1 終止。如果 向下進行一步就是：

前面再加上 (4) ，整個過程 就是 歐幾里得輾轉相除法，因此 r_k 為 Mᵢ 和 mᵢ 的 最大公約數，而 m₁, m₂, ..., m_n 是 兩兩互素，於是有： r_k = (Mᵢ, mᵢ) = 1 ，這樣就證明了 最後 總可以 終止於 1 的正確性。

接著，定義兩個數列：

有：

即，

假設，

則：

這樣歸納的證明了 (7) 成立。

當 k 為偶數時 有：

於是：

比較 (5) 得到：

當 k 為奇數時，則 k + 1 是偶數，這就要算到 (6) ，對 (6) 稍作變形：

於是，令，

並重新令：

則有：

這樣我們就將 輾轉相除 又延長了一步 到 k + 1，這時 k + 1 是偶數，則同理上面 情況 可得到：

因為此演算法最後總會終止於 1，所以 被 秦九韶 稱為『大衍求一術』，字首 “大衍” 來自於《易經 · 繫辭》：“大衍之數五十，... ...”。

當然，中國剩餘定理 要求 m₁, m₂, ..., m_n 必須兩兩 互素，對於那些 不滿足這個條件的 一次同餘方程組 可以轉換為 和 其 同解 的 滿足這個條件的 一次同餘方程組。下面舉例說明：

有一筐鴨蛋，1個1個數，正好數完；2個2個數，還剩1個；3個3個數，正好數完；4個4個數，還剩1個；5個5個數，還剩1個；6個6個數，還剩3個；7個7個數，正好數完；8個8個數，還剩1個；9個9個數，正好數完。請問：框裡最少有多少個鴨蛋？

按照題目所述，列同餘方程組如下：

顯然 1, 2, 3, 4, 5, 6, 7, 8, 9 並不兩兩互素，因此需要簡化：

一個數字必然被 1 整除，因此 ① 沒有意義，刪除； 一個數字被 9 整除，必然會被 3 整除，因此 保留 ⑨ 刪除 ③；一個數字 被 8 除餘 1，則可以表示為 8x + 1，進而有 2(4x) + 1，4(2x) + 1，於是 x 一定 可以被 2 和 4 整除，因此 保留 ⑧ 刪除 ② 和 ④；目前已經保證了 被 2 除 餘 1，可表示為 2x + 1，也保持了 被 3 整除，於是有 3(2x + 1) = 6x + 1，這說明 目前已經保持了 被 6 除 餘 3，因此 ⑥ 可以被刪除；最後剩下 ⑤ 和 ⑦ 保留。得到：

則 (8") 和 (8) 等價。由於 5,7,9,8 兩兩互素，符合 中國剩餘定理 要求，於是解：

◆M = m₁ m₂ m₃ m₄ = 5 × 7 × 8 × 9 = 2520

◆M₁ = 7 × 8 × 9 = 504

M₁ = q m₁ + r, 504 = 100 × 5 + 4 , c₀ = 1;

m₁ = q₁ r + r₁, 5 = 1 × 4 + 1, c₁ = q₁ = 1; (r₁ = 1，下標 1 是奇數，需要再算一步 )

r = q₂ r₁ + r₂, 4 = 3 × 1 + 1, c₂ = q₂c₁ + c₀ = 3 × 1 + 1 = 4；(得到結果)

M₁⁻¹ = 4， M₁⁻¹ M₁a₁ = 4 × 504 × 1 = 2016；

◆ 由於 a₂ = 0 所以 M₂⁻¹ M₂a₂ = 0；

◆M₃ =5 × 7 × 9 = 315

M₃ = q m₃ + r, 315 = 39 × 8 + 3 , c₀ = 1;

m₃ = q₁ r + r₁, 8 = 2 × 3 + 2, c₁ = q₁ = 2;

r = q₂ r₁ + r₂, 3 = 1 × 2 + 1, c₂ = q₂c₁ + c₀ = 1 × 2 + 1 = 3；(r₂ = 1，下標 2 是偶數，得到結果)

M₂⁻¹ = 3， M₂⁻¹ M₂a₂ = 3 × 315 × 1 = 945；

◆由於 a₄ = 0 所以 M₄⁻¹ M₄a₄ = 0；

得到：

x = M₁⁻¹ M₁a₁ + M₂⁻¹ M₂a₂ + M₄⁻¹ M₄a₄ = 2016 + 0 + 945 + 0 = 2961

x > M, x = x - M = 2961 - 2520 = 441

最終答案：框裡最少有 441 個鴨蛋。

最後，需要說明的是：

數學大神尤拉和高斯 對於 一般一次同餘式進行了詳細研究，獨立的得到了 中國剩餘定理，後來證實 與 秦九韶『大衍求一術』相同，於是才命名該定理為：中國剩餘定理。

中國剩餘定理，在《抽象代數》中還有另外的形式，不過這就扯遠了，就此打住。