想請教各位~~有題年齡計算問題
▲爺爺的年齡除以3會餘2，除以5可以整除，除以7會餘2，請問爺爺年齡幾歲？
請問此題目有正確算式嗎？如何算呢？不是一直用推論的~~
謝謝！
[ 想法 ]▲爺爺的年齡除以3會餘2，除以5可以整除，除以7會餘2，請問爺爺年齡幾歲？
請問此題目有正確算式嗎？如何算呢？不是一直用推論的~~
謝謝！
這類型的題目最簡單的作法就是先用推論的方式 , 放鬆條件 , 一開始先考慮一個條件 , 接下來再考慮在此條件之下 , 又能符合第二個條件的數有哪些 , 例如一開始可以考慮被5整除的case , 有 5 , 10 , 15 , 20 , 25 , 30 ... 等等 , 接下來考慮在這些數字裡面有哪些除以 3 會餘 2 , 如 5 , 20 , 35 , 50 , 65 ... 等等 , 然後再看看這些數字中哪些除以 7 會餘 2 , 可以很簡單就推到答案 .
一般常見的數學算法會使用到中國餘數定理 (Chinese Remainder Theorem) , 大致的作法的流程如下 ,
先建構出一個 5 和 7 的公倍數 , 使得他除以 3 會餘 1 , 很明顯的 , 這個數是 70
再建構出一個 3 和 7 的公倍數 , 使得他除以 5 會餘 1 , 很明顯的 , 這個數是 21
最後建構出一個 3 和 5 的公倍數 , 使得他除以 7 會餘 1 , 很明顯的 , 這個數是 15
接著分別乘上題目對應的餘數 ,
70*2 + 21*0 + 15 * 2 = 140+30 = 170
170 其實已經滿足題目的條件了 , 但一般來講 , 我們想要找的是最小的 , 所以我們要另外去取 170 對 105 的餘數 得到了 65 , 其中 105 = 3*5*7
所以爺爺的年紀就是 65 歲 .
[算式]
x = 2 (mod 3) = 0 (mod 5 ) = 2 (mod 7 )
令 a1 = 2 , m1 = 3 , a2 = 0 , m2 = 5 , a3 = 2 , m3 = 7 ,
M = m1 * m2 * m3 = 3*5*7 = 105
M1 = M / m1 = 105 / 3 = 35
M2 = M/ m2 = 105/5 = 21
M3 = M/m3 = 105/7 = 15
M1*M1-1 = 1(mod a1)
所以 , M1-1 = 2 , M2-1 = 1 , M3-1 = 1
根據中國餘數定理
x = a1 M1M1-1+a2M2 M2-1+a3M3 M3-1 mod M= (2*35*2+0+2*15) mod 105 = 170 mod 105 = 65
所以爺爺是 65歲
全站熱搜
留言列表