我國古代數學名著《孫子算經》載有一道數學問題:“今有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?”這里的幾何指多少的意思。翻譯成數學語言就是:求正整數N,使N除以3余2,除以5余3,除以7余2。
如何求符合上述條件的正整數N呢?《孫子算經》給出了一個非常有效的巧妙解法。術曰:“三、三數之剩二,置一百四十;五、五數之剩三,置六十三;七、七數之剩二,置三十,并之,得二百三十三。以二百一十減之,即得。凡三、三數之剩一,則置七十;五、五數之剩一,則置二十一;七、七數之剩一,則置十五。一百六以上,一百五減之,即得。”
過了一千多年,到了十六世紀,數學家程大位在他所著的《算法統(tǒng)宗》里把這個問題的解法用歌訣形式表述出來。三人同行七十稀, 五樹梅花廿一枝,七子團圓正月半,除百零五便得之。
歌訣的前三句給出了三組數,后一句給出了一個數:
3 70
5 21
7 15
105
三組數的共同特征是:
70除以3余1,除以5、7余0; 21除以5余1,除以3、7余0; 15除以7余1,除以3、5余0。
首先程大位把不同的余數問題統(tǒng)一化為標準的余數問題。然后,他把復雜難解的問題化解為三個易解的問題。70、21、15分別是滿足第一、二、三行條件的最小解。
2×70滿足原題第一個余數條件,且被5、7整除。
3×21滿足原題第二個余數條件,且被3、7整除。
2×15滿足原題第三個余數條件,且被3、5整除。
統(tǒng)統(tǒng)相加得和:N=2×70+3×21+2×15=233。
N必然滿足原題所有三個余數條件。但N不一定是最小的。歌訣最后一句“除百零五便得知”,這里“除”的意思是“減”,意即從233中減去3、5、7的最小公倍數105的倍數便得到23。這個23就是問題的最小解。這最后一句也可以理解為N除以105的余數就是問題的最小解。