例1:一個數(shù)被3除余1,被4除余2,被5除余4,這個數(shù)最小是幾?
題中3、4、5三個數(shù)兩兩互質。
則〔4,5〕=20;〔3,5〕=15;〔3,4〕=12;〔3,4,5〕=60。
為了使20被3除余1,用20×2=40;
使15被4除余1,用15×3=45;
使12被5除余1,用12×3=36。
然后,40×1+45×2+36×4=274,
因為,274>60,所以,274-60×4=34,就是所求的數(shù)。
例2:一個數(shù)被3除余2,被7除余4,被8除余5,這個數(shù)最小是幾?
題中3、7、8三個數(shù)兩兩互質。
則〔7,8〕=56;〔3,8〕=24;〔3,7〕=21;〔3,7,8〕=168。
為了使56被3除余1,用56×2=112;
使24被7除余1,用24×5=120。
使21被8除余1,用21×5=105;
然后,112×2+120×4+105×5=1229,
因為,1229>168,所以,1229-168×7=53,就是所求的數(shù)。
例3:一個數(shù)除以5余4,除以8余3,除以11余2,求滿足條件的最小的自然數(shù)。
題中5、8、11三個數(shù)兩兩互質。
則〔8,11〕=88;〔5,11〕=55;〔5,8〕=40;〔5,8,11〕=440。
為了使88被5除余1,用88×2=176;
使55被8除余1,用55×7=385;
使40被11除余1,用40×8=320。
然后,176×4+385×3+320×2=2499,
因為,2499>440,所以,2499-440×5=299,就是所求的數(shù)。
例4:有一個年級的同學,每9人一排多5人,每7人一排多1人,每5人一排多2人,
這個年級至少有多少人?
題中9、7、5三個數(shù)兩兩互質。
則〔7,5〕=35;〔9,5〕=45;〔9,7〕=63;〔9,7,5〕=315。
為了使35被9除余1,用35×8=280;
使45被7除余1,用45×5=225;
使63被5除余1,用63×2=126。
然后,280×5+225×1+126×2=1877,
因為,1877>315,所以,1877-315×5=302,就是所求的數(shù)。
例5:有一個年級的同學,每9人一排多6人,每7人一排多2人,每5人一排多3人,問這個年級至少有多少人?
題中9、7、5三個數(shù)兩兩互質。
則〔7,5〕=35;〔9,5〕=45;〔9,7〕=63;〔9,7,5〕=315。
為了使35被9除余1,用35×8=280;
使45被7除余1,用45×5=225;
使63被5除余1,用63×2=126。
然后,280×6+225×2+126×3=2508,
因為,2508>315,所以,2508-315×7=303,就是所求的數(shù)。
(例5與例4的除數(shù)相同,那么各個余數(shù)要乘的“數(shù)”也分別相同,所不同的就是最后兩步。)
“中國剩余定理”簡介:
我國古代數(shù)學名著《孫子算經》中,記載這樣一個問題:“今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何?!庇矛F(xiàn)在的話來說就是:“有一批物品,三個三個地數(shù)余二個,五個五個地數(shù)余三個,七個七個地數(shù)余二個,問這批物品最少有多少個?!边@個問題的解題思路,被稱為“孫子問題”、“鬼谷算”、“隔墻算”、“韓信點兵”等等。
那么,這個問題怎么解呢?明朝數(shù)學家程大位把這一解法編成四句歌訣:
三人同行七十(70)稀,五樹梅花廿一(21)枝,
七子團圓正月半(15), 除百零五(105)便得知。
歌訣中每一句話都是一步解法:第一句指除以3的余數(shù)用70去乘;第二句指除以5的余數(shù)用21去乘;第三句指除以7的余數(shù)用15去乘;第四句指上面乘得的三個積相加的和如超過105,就減去105的倍數(shù),就得到**了。即: 70×2+21×3+15×2-105×2=23
《孫子算經》的“物不知數(shù)”題雖然開創(chuàng)了一次同余式研究的先河,但由于題目比較簡單,甚至用試猜的方法也能求得,所以尚沒有上升到一套完整的計算程序和理論的高度。真正從完整的計算程序和理論上解決這個問題的,是南宋時期的數(shù)學家秦九韶。秦九韶于公元1247年寫成的《數(shù)書九章》一書中提出了一個數(shù)學方法“大衍求一術”,系統(tǒng)地論述了一次同余式組解法的基本原理和一般程序。
從《孫子算經》到秦九韶《數(shù)書九章》對一次同余式問題的研究成果,在19世紀中期開始受到西方數(shù)學界的重視。1852年,英國傳教士偉烈亞力向歐洲介紹了《孫子算經》的“物不知數(shù)”題和秦九韶的“大衍求一術”;1876年,德國人馬蒂生指出,中國的這一解法與西方19世紀高斯《算術探究》中關于一次同余式組的解法完全一致。從此,中國古代數(shù)學的這一創(chuàng)造逐漸受到世界學者的矚目,并在西方數(shù)學史著作中正式被稱為“中國剩余定理”。