韋 磊

先來看一道出自2019年重慶二診的算法題：

【原題】 把“正整數(shù)N除以正整數(shù)m后的余數(shù)為n”記為N=n（modm），例如8=2（mod3），執(zhí)行圖1所示的程序框圖后，輸出的i值為（ ）

A.32 B.35 C.37 D.39

這道題本身倒是不難，只要弄清楚“N=n（modm）”的含義即可，大不了四個(gè)選項(xiàng)一個(gè)個(gè)驗(yàn)證也是沒什么難度的.

不過聰明的同學(xué)可能會(huì)直接計(jì)算出答案：5×7+2=37.

因?yàn)轱@然，5×7+2這個(gè)式子是滿足除以5余2，而且除以7也余2的.

如果發(fā)散思維，那么下面這個(gè)問題的答案也就呼之欲出：

【變式1】 如果正整數(shù)N除以a余k，除以b余k，除以c余k，其中a，b，c互質(zhì)，那么滿足條件的N可以是多少？

答案很顯然，就是N=abc+k.

緊接著的問題就自然有了：當(dāng)余數(shù)不一樣時(shí)又該如何？

【變式2】 如果正整數(shù)N除以5余2，除以7余4，求滿足條件的其中一個(gè)N.

我們可以通過這樣的方法來找N：

（1）在7的倍數(shù)中找除以5余2的數(shù).

你很快就能找出來，因?yàn)?本身就是.

（2）在5的倍數(shù)中找除以7余4的數(shù).

這個(gè)可以一個(gè)一個(gè)試，不過我們有更好的方法來找.那就先找除以7余1的數(shù)，很幸運(yùn)，15就是.那么15×4就一定是除以7余4的數(shù).

（3）將這兩個(gè)數(shù)相加.

因此7+15×4=67就一定是既滿足除以5余2，又滿足除以7余4的數(shù).

當(dāng)然，我們可以在這個(gè)數(shù)的基礎(chǔ)上加上或者減去5和7的最小公倍數(shù)，也是滿足條件的.反正你加上一個(gè)能被5和7整除的數(shù)又不會(huì)影響到余數(shù).

所以67-35=32也是滿足條件的.經(jīng)檢驗(yàn)，確實(shí)如此.

圖1

練習(xí) 正整數(shù)N除以3余2，除以11余4，求滿足條件的N的最小值.

答案：26.

解決了這一問題，更深一層次的問題緊接而來，我們以著名的韓信點(diǎn)兵問題為例.該問題說：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？

此題轉(zhuǎn)化為現(xiàn)代數(shù)學(xué)語言便是：

【變式3】 如果正整數(shù)N除以3余2，除以5余3，除以7余2，則滿足條件的N的最小值為多少？

對(duì)此，我們可以按照下面的方式解決：

（1）在3和5的最小公倍數(shù)中找除以7余2的數(shù).

運(yùn)氣不太好，3×5=15并不是.那就先找除以7余1的數(shù)，15這個(gè)數(shù)剛好滿足，于是15×2=30就一定是除以7余2的數(shù).

（2）在5和7的公倍數(shù)中找除以3余2的數(shù).

很幸運(yùn)，5×7=35也剛好是.

（3）在3和7的公倍數(shù)中找除以5余3的數(shù).

這不太幸運(yùn)了，3×7=21不是.那就先找除以5余1的數(shù)，也就剛好是這個(gè)21了.

于是21×3=63就一定是除以5余3的數(shù).

（4）把三個(gè)數(shù)相加.

即3×5×2+5×7+3×7×3=128就是滿足條件的N.經(jīng)檢驗(yàn)確實(shí)如此.

然后可以在128這個(gè)數(shù)的基礎(chǔ)上加上或者減去“3，5，7”的最小公倍數(shù)，得到的數(shù)同樣滿足條件.

所以最小的N為128-3×5×7=23.

這就是著名的“物不知其數(shù)”問題了，專業(yè)術(shù)語也叫“一次同余問題”，相應(yīng)的結(jié)論被稱為“中國剩余定理”或者“孫子定理”.

在《孫子算經(jīng)》中，當(dāng)然不是以此類數(shù)學(xué)語言作為解答，而是以一首詩，沒錯(cuò)，就是一首詩：

三人同行七十?。晃鍢涿坊ㄘヒ恢?；七子團(tuán)圓正半月；除百零五便得知.

“三人同行七十稀”的意思，就是用除以3的余數(shù)來乘以70，也就是70×2；“五樹梅花廿一枝”意為用除以5的余數(shù)來乘以21，得到3×21了；“七子團(tuán)圓正半月”便是用除以7的余數(shù)來乘以15，就是為2×15；“除百零五便得知”就是減去整數(shù)個(gè)105.最后一句中的百零五，就是3，5，7的最小公倍數(shù).

寫作現(xiàn)代數(shù)學(xué)式子，此題答案便是70×2+3×21+2×15-105n=233-105n.取n=2的時(shí)候，便是我們?cè)谇懊嫠玫降淖钚≈?3.

那么這首答案詩具體為何意？且看那個(gè)70，這個(gè)數(shù)就是5和7的倍數(shù)，而且除以3后余1，那么70×2便是5和7的倍數(shù)中，除以3余2的那個(gè)數(shù)了；同理可以理解后面的3×21和2×15.

這與我們的解法，本質(zhì)完全相同.你還能感受到古代數(shù)學(xué)家兼有的詩人氣息，所謂數(shù)學(xué)如詩，便是如此.

為了便于描述，我們啟用題目給出的“N≡n（modm）”這一符號(hào).

還是以【變式3】為例，題目相當(dāng)于解方程組：

利用【變式2】中的方法，可以算的第一個(gè)方程和第二個(gè)方程的解為23+15k，這不就是表示這個(gè)數(shù)除以15余23的意思嘛，所以這個(gè)解寫成x≡23（mod15）.

于是原方程相當(dāng)于解：

再按照相同的方法算得這個(gè)方程的解為x=23+105k.

我們因此就找到了這類問題較為便捷的解決方法.姑且叫做“消元法”吧！

我們來一個(gè)問題練練手，一個(gè)與韓信點(diǎn)兵問題等價(jià)的問題，題目的意思，就是找一個(gè)數(shù)x，使得其除以5余1，除以6余5，除以7余4，除以11余10，除以13余5.

練習(xí) 解方程

解 我們先找余數(shù)相同的方程，畢竟這屬于【變式1】的內(nèi)容，很好處理.第二個(gè)方程和最后一個(gè)方程就是，其一個(gè)解為6×13+5=83，所以其解可以表示為x=83（mod78），實(shí)際上也可以寫出x=5（mod78），減去一個(gè)78嘛.

第一個(gè)方程和第三個(gè)方程就是在5的倍數(shù)找除7余1的數(shù)，以及在7的倍數(shù)中找除5余1的數(shù).利用我們連分?jǐn)?shù)的方法，解得其中的兩個(gè)解為3×5=15和3×7=21，于是5的倍數(shù)中除7余4的數(shù)就是15×4=60，7的倍數(shù)中除以5余1的數(shù)就是21.于是60+21=81就是這兩個(gè)方程的一個(gè)解，自然11也就是，減去兩個(gè)35嘛！

所以第一個(gè)方程和第三個(gè)方程的解為：x=11（mod35）

整個(gè)方程化簡(jiǎn)為：

再次解第二個(gè)和第三個(gè)方程的解為：x=186（mod385），其解決過程就給各位當(dāng)成練習(xí)了，所以方程組化為：

然后就解得該方程的其中一個(gè)解為x=3275381.

下期預(yù)告：通讀全文不難看出，解決【變式3】的關(guān)鍵就是如何找到“3和5的最小公倍數(shù)中除以7余1”的數(shù)，這個(gè)問題其實(shí)就和秦九韶的大衍求一術(shù)密切相關(guān)，想知道更多精彩內(nèi)容嗎？下期再見.