韩信点兵中国剩余定理.ppt

學科講話…延續篇 韓信點兵法 / 中國剩餘定理 韓信點兵法 / 中國剩餘定理 根據「孫子算經」記載︰ 「今有物，不知其數，三三數之，剩二，五五數之，剩三，七七數之，剩二，問物幾何？」 韓信點兵法 / 中國剩餘定理 設該數為 X 韓信點兵法 / 中國剩餘定理 韓信點兵法 / 中國剩餘定理 韓信點兵法 / 中國剩餘定理 韓信點兵法 / 中國剩餘定理 韓信點兵法 / 中國剩餘定理 韓信點兵法 / 中國剩餘定理 韓信點兵法 / 中國剩餘定理 韓信點兵法 / 中國剩餘定理 * * 今有物，不知其數，三三數之，剩二， 五五數之，剩三，七七數之，剩二，問物幾何？ 根據題目資料： X = 3a + 2 X = 5b + 3 X = 7c + 2 X 的數值是什麼？ 思路分析： 據以下觀察，這條題目不應只得一個解。 443 = 3 x 147+2 443 = 5 x 88+3 443 = 7 x 63+2 今有物，不知其數，三三數之，剩二， 五五數之，剩三，七七數之，剩二，問物幾何？ 548 = 3x182+2 548 = 5x109+3 548 = 7x78+2 653 = 3x217+2 653 = 5x130+3 653 = 7x93+2 今有物，不知其數，三三數之，剩二， 五五數之，剩三，七七數之，剩二，問物幾何？ 從上述例子得知： 443，548，653… 均可是題目的解。 由於 443，548 及 653均是經過 3、5、7 的倍數構造出來，所以，我們雖不能從題目得知確實的答案，但可推斷所有有可能的答案之間的相距應該是3、5、7 的最小公倍數(LCM)，即105的倍數。 今有物，不知其數，三三數之，剩二， 五五數之，剩三，七七數之，剩二，問物幾何？ 問題：既然題目是有很多的解， 那麼，最小的一個正數解 是多少？ 由於運算複雜，所以，古時有以下歌訣把重要步驟及數字紀錄下來： 三 人 同 行 七 十 稀， 五 樹 梅 花 廿 一 枝， 七 子 團 圓 正 月 半， 除 百 零 五 便 得 知。 三人同行七十稀：70 ? 3 餘 1 五樹梅花廿一枝：21 ? 5 餘 1 七子團圓正月半：15 ? 7 餘 1 除百零五便得知：解與解相距是 105的倍數 三 人 同 行 七 十 稀，五 樹 梅 花 廿 一 枝， 七 子 團 圓 正 月 半，除 百 零 五 便 得 知。 所以 (2 x 70) ? 3 餘 2 ； (3 x 21) ? 5 餘 3； (2 x 15 )? 7 餘 2 由於 70 ? 3 餘 1， 21 ? 5 餘 1，15 ? 7 餘 1 ， X = 3a + 2 X = 5b + 3 X = 7c + 2 從上述結果，我們得知： (2 x 70) ? 3 餘 2 ； (3 x 21) ? 5 餘 3；(2 x 15 )? 7 餘 2 由於 70 = 5 x 7 x 2 ( 70 能被 5 和 7 整除 ) 21 = 7 x 3 ( 21能被 3 和 7 整除 ) 15 = 3 x 5 ( 15能被 3 和 5 整除 ) 所以， (2 x 70) + (3 x 21) + (2 x 15 ) = 233 除以 3 餘 2 ；除以 5 餘 3 ；除以 7 餘 2 。 三 人 同 行 七 十 稀，五 樹 梅 花 廿 一 枝， 七 子 團 圓 正 月 半，除 百 零 五 便 得 知。 233 是符合題目的其中一個解。 由於解與解相距是105的倍數，所以 233 – 105 – 105 = 23 便是題目的最小的正數解。 除 百 零 五 便 得 知