一個(gè)數(shù)除以3余2,除以5余3,除以7余2,求適合這個(gè)條件的最小數(shù).孫子的解法是:
先從3和5、3和7、5和7的公倍數(shù)中相應(yīng)地找出分別被7、5、3除均余1的較小數(shù)15、21、70 ( 注釋:此步又稱為求"模逆"運(yùn)算,利用擴(kuò)展歐幾里得法并借助計(jì)算機(jī)編程可比較快速地求得.當(dāng)然,對(duì)于很小的數(shù),可以直接死算 ).即
15÷7=2……余1,
21÷5=4……余1,
70÷3=23……余1.
再用找到的三個(gè)較小數(shù)分別乘以所要求的數(shù)被7、5、3除所得的余數(shù)的積連加,
15×2+21×3+70×2=233. (將233處用i代替,用程序可以求出)
最后用和233除以3、5、7三個(gè)除數(shù)的最小公倍數(shù).
233÷105=2……余23,
這個(gè)余數(shù)23就是合乎條件的最小數(shù).
以上三個(gè)步驟適合于解類似"孫子問題"的所有問題.