最小公倍數與最大公因數

Question

有一數 用3除餘1 用5除餘2 用7除餘3 問此數為多少

Answer 1

這是一個「中國餘數定理」的典型題目！

中國餘數定理：

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

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

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

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

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

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

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

「餘１」奶奶回答。

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

「整除」奶奶回答。

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

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

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

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

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

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

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

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

有一數 用3除餘1 用5除餘2 用7除餘3 問此數為多少 ？

設總數為ｋ，把÷3後的餘數，要乘的常數為ａ
÷5後的餘數，要乘的常數為ｂ
÷7後的餘數，要乘的常數為ｃ
且ａ，ｂ，ｃ＜１０５，即可列出式子：

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

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

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

所以ａ＝７０　ｂ＝２１　ｃ＝１５

即ｋ＝ａ＋２ｂ＋３ｃ＝７０＋４２＋４５－１０５＝５２（最小的符合條件正整數）

（驗算一下，除除看，答案是否正確？）

５２÷３＝１７餘１
５２÷５＝１０餘２
５２÷７＝７餘３

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

2006-11-03 20:15:40 補充：
更正：ａ＝〔７，５〕×ｘ　ａ÷３……１ｂ＝〔７，３〕×ｙ且ｂ÷５……１ｃ＝〔５，３〕×ｚ　ｃ÷７……１

2006-11-03 20:20:38 補充：
其實：５２只是符合條件的最小正整數只要是１０５的正倍數＋５２都可以符合條件！（因為沒有規定所求範圍）這種中國餘數定理題目一般來說，只討論正整數。所以１０５的負倍數，不在此範圍內。且上述ｘ，ｙ，ｚ皆為正整數。

2006-11-03 20:23:15 補充：
當然，「 不停回答的傢伙 」的回答，是正確的，但是碰上１０００以上的數。不知要算到什麼時候‧‧‧‧

Answer 2

到下面的網址看看吧

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

Answer 3

(-35a+21b+15c) 是怎麼來的阿

Answer 4

有一整數，用3除餘a，用5除餘b，用7除餘c，
則此數的一個特解為(-35a+21b+15c)

代進去，
-35*1+21*2+15*3
=-35+42+45
=52
這就是答案！！

2006-11-04 21:19:47 補充：
用中國剩餘定理配合同餘式算出來的。

Answer 5

因為有5，所以各位數只能有3&7而以。
所以此數為52
因 52除以3=17...1
52除以5=10...2
52除以7=7...3

Answer 6

先把用3除 餘1的數列出來
1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55.......
再把用5除 餘的數列出來
2 7 12 17 22 27 32 37 42 47 52 57 62.......
最後再把用7除 餘3的數列出來
3 10 17 24 31 38 45 52 59......

所以答案是52

2006-11-05 11:33:06 補充：
因為我不知道你試問最小還是只是要數而已只要那個數的話 就把算出來的數加上那些數的公倍數就像52+3*5*7也就是52+105N N為常數

Answer 7

設此數=3Q+1 (將Q除以5得商q餘r ,且0≦r＜5 )
=3( 5q+r) + 1
=15q + 3r + 1 (用r=0,1,2,3,4分別代入僅2符合被5除餘2)
=15q + 7 (將q除以7得商 q` 餘 r`,且0≦r`＜7 )
=15( 7q` + r`) + 7
=105 q` + 15r` + 7 (用r`=0,1,2,3,4,5,6分別代入僅3符合被7除餘3)
= 105 q` + 52
故此數通解為 105 q` + 52 ( q` 為任意整數 )

Answer 8

我算出來是５２５２／３＝１７．．．餘１５２／５＝１０．．．餘２５２／７＝　７．．．餘３我用最小公倍數跟最大公因數算不出來５２是推出來的！