鄭濤（Tao Steven Zheng）著

【問題】

以下是一個著名的數(shù)論問題，來自《孫子算經(jīng)》（活在公元 3 - 5 世紀(jì)）。這道題有涉及到模算術(shù)（modular arithmetic）、模逆（modular inverse）、兩兩互素（coprime）、中國剩余定理（Chinese remainder theorem）等數(shù)論概念。

【原文】

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

【今譯】

假設(shè)有些物，不知其數(shù)量。三個三個去數(shù)，剩下 2 個；五個五個去數(shù)，剩下 3 個；七個七個去數(shù)，剩下 2 個。問：物的數(shù)量是多少？

（求最小正整數(shù)解）

【題解】

這個問題是一個具有無窮多解的不定方程組。根據(jù)題意，得

注：同余式 表示 除以 剩余 ，亦即 為整數(shù)。稱 為模數(shù)（modulus）， 為余數(shù)（remainder）。

因?yàn)?3、5、7 都是兩兩互素（coprime 或 relatively prime）模數(shù)，我們只用計(jì)算模數(shù)（modulus）的乘積：

中國剩余定理（Chinese remainder theorem）的解規(guī)定

對于這個問題

和

其中

? 表示每個余數(shù)的模逆（modular inverse）。利用秦九韶 (1202 年- 1261 年) 的大衍求一術(shù)可以系統(tǒng)地求解模逆; 不過，這個問題涉及的數(shù)字很小，可以通過猜測和檢查得到。

計(jì)算

對于這個問題，233確實(shí)是一個解，但這不是最小正整數(shù)解。

最小正整數(shù)解為 23。

《孫子算經(jīng)》的答案與解法

【原文】

答曰：二十三。

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

【今譯】

答案：23。

解法：“三個三個去數(shù)，剩下2個”布置 140?！拔鍌€五個去數(shù)，剩下 3 個” 布置 63?！捌邆€七個去數(shù)，剩下 2 個”布置 30。把這些數(shù)并起來得到 233。然后減去 210 得到答案。當(dāng)三個三個去數(shù)，布置 70，得到1的余數(shù)。當(dāng)五個五個去數(shù)，布置 21，得到 1 的余數(shù)。當(dāng)七個七個去數(shù)，布置 15 得到 1 的余數(shù)。當(dāng)結(jié)果是 106 以上，以 105 減去得到答案。