2017.2.26. 邵啟鼎

一、題目

       一筐雞蛋：1個1個拿，正好拿完；2個2個拿，還剩1個；3個3個拿，正好拿完；4個4個拿，還剩1個；5個5個拿，還差1個；6個6個拿，還剩3個；7個7個拿，正好拿完；8個8個拿，還剩1個；9個9個拿，正好拿完。問：筐里最少有多少個雞蛋？

二、答案

        此題見于微信群聊。發(fā)帖人把能解此題的人稱做智商不一般的“高手”，附言說 “有高手沒？算算吧！算不出轉(zhuǎn)發(fā)其他群，看看哪個群里高手多”。經(jīng)激將，終于有“高手”絞盡腦汁給出了答案：1449個。這個數(shù)字經(jīng)驗算是正確的。問題是：它是怎么得來的；是否滿足了“最少”的條件?？磥?如果缺少必要的推算步驟，那么問題仍不能算作已經(jīng)解決。

三、題析

       此題從逐個拿到9個9個拿共有9個剩余條件。但是第一個條件無意義，因為雞蛋不管有多少，1個1個拿都不會有剩。第二個條件只指出答案應是單數(shù)，況且已知4個4個拿和8個8個拿都剩1個，所以也無多大意義。接下來，第三和第四個條件也是多余的，因為9個9個拿既然能正好拿完，那么3個3個拿也必定正好拿完；8個8個拿既然還剩一個，那么4個4個拿也必定只剩一個。如此說來，對解題有意義的只是從5開始的五種拿法、五個條件。

       另外，雞蛋只能論個，所以這里涉及的都是正整數(shù)。據(jù)此，本題在本質(zhì)上可以改述為：求一個最小的正整數(shù)，它除以5余4，除以6余3，除以7余0，除以8余1，除以9余0。

       雖然整數(shù)的除法連小學生都會，但是你要是從9開始把正整數(shù)一個個拿來試的話，那就太費時間了，即使每天試算100個數(shù)，也需兩星期才能試出，而且還不能有錯?？磥淼昧硐朕k法。

       辦法是有的，不過要用到同余理論。如果你還不知道何為同余，那么下一節(jié)就不能跳過不看。

四、理論

    （一）有關(guān)概念

       整數(shù)相除，只要不能整除，就會產(chǎn)生余數(shù)。反之，整除可以看成余數(shù)為零的特殊情況。

       同余指的是兩個整數(shù)分別除以同一個整數(shù)時所得的余數(shù)相同。例如26和14除以6的余數(shù)都是2，于是稱26和14在除數(shù)為6時同余。如果用符號≡表示同余，用括號（）來補充說明除數(shù)是多少，則上述的同余關(guān)系可以寫成：26≡14(mod 6)。這里的英語單詞mod可以音譯成“模”，模指的就是除數(shù)。

       推而廣之，在一般情況下，只要兩個整數(shù)a與b分別除以同一個整數(shù)n而同余，則可用數(shù)學式子表達為a≡b(mod n)，讀作“a和b對模n同余”（模n，就是說除數(shù)是n）。像這種表達同余關(guān)系的數(shù)學式就叫做同余式。它有點像等式，但a=b是相等關(guān)系，而a≡b則是同余關(guān)系。26≡14 的意思絕不是說兩者相等。

       在 b < n 的特殊情況下，b其實就是a÷n的余數(shù)。例如在 26≡2(mod 6)中，2直接就是26÷6的余數(shù)。所以當 b < n 時，a≡b(mod n)也可以解讀為“a除以n余b”。下面遇到的情況基本上都是如此。

       另外，以上的a、b、n都如同26、14、6一樣，被認為是已知數(shù)。一旦同余式中存在未知數(shù)，那么這個同余式就被稱作同余方程。特別是，形如 ax≡b(mod n) 的方程，由于未知數(shù)x的次數(shù)只是一次，所以專門稱作一次同余方程，或線性同余方程。

    （二）對線性同余方程是否有解的判決

       若有一個線性同余方程am≡b(mod n)，其中a、b、n都是已知數(shù)，m是未知數(shù)，我們怎樣得知它有沒有解，以及有解的話有幾個解呢？判決的規(guī)則是這樣的：假如a和n的最大公約數(shù)是d，而d又能整除b，那么方程就有解，而且恰好有d個解。

        例如在方程 3m≡2(mod 6) 中，3和6的最大公約數(shù)是3，但3不能整除2，所以方程無解。

        再如方程 4m≡2(mod 6)。其中4和6的最大公約數(shù)是2，而2能整除2，所以方程有解，且有兩個解。

    至于解的具體求法,則因題而異。此類題的方程不只一個，而是聯(lián)立的一組。如果這組方程的幾個模兩兩互質(zhì)，那么求解就有一般的公式可以套用。但在我們的問題里，由于除數(shù)6和8、9 都不互質(zhì)，所以只能利用余數(shù)的性質(zhì)來求解。

     （三）余數(shù)的一個性質(zhì)

       設(shè)a、b和n都是正整數(shù)，且n>1，則 (a×b)÷n的余數(shù)，等于a÷n的余數(shù)乘以b÷n的余數(shù)。例如：(9×10)÷7的余數(shù)是6。而9÷7余2，10÷7余3，結(jié)果2×3=6，與乘積9×10除以7的余數(shù)同。

       余數(shù)的這個性質(zhì)可以簡述為：乘積之余等于余之乘積。

       余數(shù)的性質(zhì)有很多，我們用得上的就這一個。所用之處是：已知兩數(shù)乘積的余數(shù)以及一個乘數(shù)的余數(shù)，求出另一個乘數(shù)的余數(shù)。方法是用乘積的余數(shù)除以一個乘數(shù)的余數(shù)，不夠整除就加一次模，還不夠就再加。例如，已知9m÷7余6，其中m為正整數(shù)，問m÷7余幾？答：因為9÷7余2，而乘積的余數(shù)是6，除以乘數(shù)9的余數(shù)2得3，因而 m÷7余3，而且m至少是3。

       再如，已知3m÷4余1，問m÷4余幾？答：因為3÷4余3，而乘積的余數(shù)1除以3不夠整除，所以1需要連加兩次模數(shù)4得9才行。9÷3=3，所以m÷4余3，且m最小是3。

       有了這些理論知識，現(xiàn)在已有條件解題了。

五、題解

        設(shè)所求的數(shù)（筐里最少的雞蛋總數(shù)）為S。據(jù)題設(shè)，S能被7和9整除，所以它一定等于63的倍數(shù)，可以寫成63m，其中63=7×9是7和9的最小公倍數(shù)，而未知數(shù)m則是另一個大于1的正整數(shù)。

        又，S除以5余4，除以6余3，除以8余1。將S換作63m后，可列出線性同余方程組如下：

            63m=4(mod 5)      (1)；          63m=3(mod 6)      (2)；          63m=1(mod 8)      (3)；

     【第一步】先判斷這三個方程有沒有解，幾個解。

       按照上述的判決規(guī)則，在方程(1)中，63和5的最大公約數(shù)=1，1能整除4，所以方程(1)有解，且只有一個解；在方程(2)中，63和6的最大公約數(shù)=3，3能整除3，所以方程(2)有解，且有三個解；在方程(3)中，63和8的最大公約數(shù)=1，1能整除1，所以方程(3)有解，且只有一個解。

     【第二步】運用余數(shù)性質(zhì)，分別求出三個方程中m對不同模的余數(shù)。

       在方程(1)中，因為乘積63m÷5余4，而乘數(shù)63÷5余3，所以m÷5應該余：(4+1×5)÷3=3。

       在方程(2)中，因為乘積63m÷6余3，而乘數(shù)63÷6余3，所以在0到5的范圍內(nèi)m÷6的余數(shù)可以是：(3+0×6)÷3=1，或(3+1×6)÷3=3，或(3+2×6)÷3=5。這個結(jié)果符合方程(2)有三個解（即m可以有三個值）的判決。

       在方程(3)中，乘積63m÷8余1，但乘數(shù)63÷8余7，而1不能被7整除，需連加6次8得49才行。所以m÷8應該余：(1+6×8)÷7=7。

       現(xiàn)在問題可以進一步歸結(jié)為：求一個正整數(shù)m，它除以5余3，除以6余1或3或5，除以8余7。

    【第三步】求同時滿足這三個剩余條件的m值。

       為簡單計，先在m÷6的三個可能的余數(shù)中取5，即設(shè)m÷6余5。這時應注意到m÷8余7，就是說，m只要加上1，就能同時被6和8整除。而6和8的最小公倍數(shù)是24，所以m最小等于24 -1=23。經(jīng)驗算，m=23這個結(jié)果同時也能滿足除以5余3的條件，所以肯定是問題的一個解。但是它是否最小，還需檢查一下當m÷6余1或余3時的情況。

     【第四步】檢查23是不是m的最小可能值。

       如果m÷6余3，那么m減去3之后就能同時被6和5整除，因為m÷5也余3。而5和6的最小公倍數(shù)是30，因而在這個剩余條件下m最小應是30+3=33。這個數(shù)已比23大10，而且還不滿足除以8余7的條件，故應舍棄。

       再看m÷6余1，這時m可以寫成6n+1，這里n是從0開始的自然數(shù)。為便于比較，滿足m÷5余3和m÷8余7這兩個條件的m也寫成這個形式，即：m=5n+3，m=8n+7。

        將n=0、1、2、3、4、5……代入，可得：

       滿足除以5余3這個條件的m的可能值有：3、8、13、18、23、28、33……

       滿足除以6余1這個條件的m的可能值有：1、7、13、19、25、31、37……

       滿足除以8余7這個條件的m的可能值有：7、15、23、31、39、47、56……

比較可知，在m÷6余1的情況下，在小于23的范圍內(nèi)，并沒有能夠同時滿足三個條件的m值，可見m=23應當是最小的解。

     【第五步】 計算最少的雞蛋總數(shù)S。

       S=63m=63×23=1449。解畢。

六、后記

       與本題同類的應用題，最早見于我國南北朝時期成書的《孫子算經(jīng)》。此書下卷的第26題現(xiàn)在被稱作“孫子問題”或“物不知數(shù)”題。題的原文是：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？”

       如果把這里的“物”具體化為雞蛋，把三三、五五、七七數(shù)之，擴展為五五、六六、七七、八八、九九數(shù)之，那么孫子問題就變成我們上面所討論的拿雞蛋的問題了。只不過孫子問題中的除數(shù)3、5、7是兩兩互質(zhì)的，因而可以有一般的解法:答數(shù) = (三三數(shù)之的余數(shù)×70+五五數(shù)之的余數(shù)×21+七七數(shù)之的余數(shù)×15) -105的倍數(shù)。

         孫子在算經(jīng)中給出的，正是上述這種不管剩幾都能適用的一般解法。而我們的問題只是就事論事，能算出滿足題設(shè)的具體數(shù)字即可。相比之下，孫子問題雖然數(shù)據(jù)簡單，但就題目的最終目的而言，它比我們拿雞蛋僅僅要求得出1449這個具體數(shù)字要困難得多。正因為如此，我們說：拿雞蛋“這道題做不出就太丟人了”。要知道，“物不知數(shù)”這類題早在一千五百年前就已經(jīng)出現(xiàn)并有人解答了。