想問中國剩餘定理的証明

Question

雖然說大概知道怎麼算

可是我想知道原理

所以請大大幫忙證明一下(不要太複雜就可以= =")...

謝謝

Answer 1

中國餘數定理：

中國餘數定理是結合了除式中的餘數和公倍數而產生的，此定理記載於孫子兵法中的韓信點兵，也是孫子算經的一部份：

韓信帶兵出征打仗，經過好一番戰鬥後，勝利歸回。可是，韓信想計算這次打仗的死傷人數，作為下一次打仗的計謀基礎。所以，韓信就把原有的人數，減掉了這次歸回的人數，就是這次傷亡的人數。

到底要怎麼樣知道這團兵團的總人數呢？由於這團兵團超過十萬人，所以不可能一個一個去數。於是韓信就把兵團整隊成ａ個、ｂ個、ｃ個、ｄ個…………………人排一排，看看各會剩下幾個人。再加以計算，就可以算出總人數啦！

而韓信到底是怎麼算的呢？

我們來舉一個簡單的例子：

有一天，小明問奶奶的年齡，奶奶不直接告訴他，於是小明就問：

「您的年齡除以３是餘多少？」

「餘１」奶奶回答。

「您的年齡除以５是餘多少？」

「整除」奶奶回答。

「您的年齡除以７是餘多少？」

「差５就能整除」奶奶回答。

「那麼，您今年是百歲大壽哦！」

「被你猜中了。」奶奶回答。

「我可不是用猜的喔！」小明回答。

這一題的算法做法很簡單，設奶奶的年齡為ｘ，求ｘ只要把÷３的餘數×７０＋（÷５的餘數）×２１＋（÷７的餘數）×１５，再依ｘ的範圍，加減最小公倍數，就算出答案了。

讀者可能會問：「那７０、２１、１５這幾個常數是從哪來的？」其實，仔細觀察一下這些數，７０是５和７的公倍數，而且除以３餘１；２１是３和７的公倍數，而且除以５餘１；１５是３和５的公倍數，而且除以７餘１；（餘１的原因是因為須符合除數除出的餘數，且在加法時，不會妨礙到其他式子運算的結果）甚至，７０，２１，１５都不會超過３，５，７的最小公倍數。而且這些常數，都是符合上述條件中的最小正整數！

既然都已經知道求常數，解餘數問題的方法了，就來實驗一下吧！

在○○國小的書法社團裡，我數了一下人數，總人數÷２整除，÷３欠１，÷５餘４，而且（０人＜總人數＜３０人）。問總人數有多少人？

設總人數為ｋ，把÷２後的餘數，要乘的常數為ａ；÷３後的餘數，要乘的常數為ｂ；÷５後的餘數，要乘的常數為ｃ；且ａ，ｂ，ｃ＜３０，即可列出三元一次方程式：

ａ＝〔３，５〕×ｘ　ａ÷２……１

ｂ＝〔２，５〕×ｙ且ｂ÷３……１

ｃ＝〔２，３〕×ｚ　ｃ÷５……１

所以ａ＝１５　ｂ＝１０　ｃ＝６

即０ａ＋２ｂ＋４ｃ＝２０＋２４＝４４

ｋ＝４４－〔２，３，５〕＝１４（驗算一下，除除看，答案是否正確？）

把這門方法代進韓信計算兵數的方法，就可以算出來了。

Answer 2

到下面的網址看看吧

▶▶http://qoozoo09260.pixnet.net/blog

Answer 3

什麼定理的証明