標題:
[MATH]INTEGERS
發問:
what is the least positive integer meeting each of the following conditions? dividing by 7 gives a remainder of 4 dividing by 8 gives a remainder of 5 dividing by 9 gives a remainder of 6
最佳解答:
這條問題,真正,而且能在大部份情況下能用的答案是中國剩餘定理。 首先留意,7,8,9三個數是兩兩互質的。就是說(7,8)沒有公因數,(7,9)沒有公因數,(8,9)也沒有公因數。這種情況,我們可以找到 除7和8都能除盡,但除9餘1的數。這個數可以用7 x 8 = 56的倍數去找,最後找到是280. 留意280 / 7 = 40, 280 / 8 = 35, 280/9 = 31...1 除7和9都能除盡,但除8餘1的數。這個數可以用7 x 9 = 63的倍數去找,最後找到是441. 留意441 / 7 = 63, 441 / 9 = 49, 441/8 = 55...1 除8和9都能除盡,但除7餘1的數。這個數可以用8 x 9 = 72的倍數去找,最後找到是288. 留意288 / 8 = 36, 288 / 9 = 32, 288/7 = 41...1 (注：除了每個倍數試之外，其實也可以使用Extended Euclidean Algorithm去找這些數，這個方法會快很多，這裏不談了） 這些數非常有用,因為我們可以用乘法和加法隨意控制餘數。 比方說,我想要一個數除7餘2,除8除9都能除盡的話,這個數就是288 x 2 = 576 又例如,我想要一個數除7餘2,除8餘1,除9能除盡的話這個數就是288 x 2 + 441 x 1 = 1017 回應題目,要求除7餘4,除8餘5,除9餘6的,答案當然就是 280 x 6 + 441 x 5 + 288 x 4 = 5037 留意,這些數加減LCM都不會影響餘數的性質,所以5037 - 504 都是可以的, 5037 - 504 * 10都是可以的。 如果要找最少而又符合題目要求的正整數,它就是501, 因為 5037 / (7 x 8 x 9) = 9 ... 501 樓上用LCM的計法是正確的,而且比較簡單。如果這是一條小學生的題目,絕對應該用他的方法。但是他是方法一定要餘數剛剛好相差的數目好整齊(4,5,6) (7,8,9)。 如果不整齊,他的方法就行不通了。我的方法則是任何兩兩互質的數都可以使用。 有關Extended Euclidean Algorithm http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm 有關中國剩餘定理 http://en.wikipedia.org/wiki/Chinese_remainder_theorem 2007-05-10 12:05:36 補充： 如果除7餘3的話，用我的方法,答案就是280 x 6 加 441 x 5 加 288 x 3 = 47494749 除 504 = 9 餘 213也能快速地找到213 2007-05-11 14:39:58 補充： 謝謝
其他解答:
[MATH]INTEGERS
發問:
what is the least positive integer meeting each of the following conditions? dividing by 7 gives a remainder of 4 dividing by 8 gives a remainder of 5 dividing by 9 gives a remainder of 6
最佳解答:
這條問題,真正,而且能在大部份情況下能用的答案是中國剩餘定理。 首先留意,7,8,9三個數是兩兩互質的。就是說(7,8)沒有公因數,(7,9)沒有公因數,(8,9)也沒有公因數。這種情況,我們可以找到 除7和8都能除盡,但除9餘1的數。這個數可以用7 x 8 = 56的倍數去找,最後找到是280. 留意280 / 7 = 40, 280 / 8 = 35, 280/9 = 31...1 除7和9都能除盡,但除8餘1的數。這個數可以用7 x 9 = 63的倍數去找,最後找到是441. 留意441 / 7 = 63, 441 / 9 = 49, 441/8 = 55...1 除8和9都能除盡,但除7餘1的數。這個數可以用8 x 9 = 72的倍數去找,最後找到是288. 留意288 / 8 = 36, 288 / 9 = 32, 288/7 = 41...1 (注：除了每個倍數試之外，其實也可以使用Extended Euclidean Algorithm去找這些數，這個方法會快很多，這裏不談了） 這些數非常有用,因為我們可以用乘法和加法隨意控制餘數。 比方說,我想要一個數除7餘2,除8除9都能除盡的話,這個數就是288 x 2 = 576 又例如,我想要一個數除7餘2,除8餘1,除9能除盡的話這個數就是288 x 2 + 441 x 1 = 1017 回應題目,要求除7餘4,除8餘5,除9餘6的,答案當然就是 280 x 6 + 441 x 5 + 288 x 4 = 5037 留意,這些數加減LCM都不會影響餘數的性質,所以5037 - 504 都是可以的, 5037 - 504 * 10都是可以的。 如果要找最少而又符合題目要求的正整數,它就是501, 因為 5037 / (7 x 8 x 9) = 9 ... 501 樓上用LCM的計法是正確的,而且比較簡單。如果這是一條小學生的題目,絕對應該用他的方法。但是他是方法一定要餘數剛剛好相差的數目好整齊(4,5,6) (7,8,9)。 如果不整齊,他的方法就行不通了。我的方法則是任何兩兩互質的數都可以使用。 有關Extended Euclidean Algorithm http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm 有關中國剩餘定理 http://en.wikipedia.org/wiki/Chinese_remainder_theorem 2007-05-10 12:05:36 補充： 如果除7餘3的話，用我的方法,答案就是280 x 6 加 441 x 5 加 288 x 3 = 47494749 除 504 = 9 餘 213也能快速地找到213 2007-05-11 14:39:58 補充： 謝謝
其他解答:
此文章來自奇摩知識+如有不便請留言告知
good!|||||Dividing by 7 gives a remainder of 4 = 11. Dividing by 8 gives a remainder of 5 = 13. Dividing by 9 gives a remainder of 6 = 15.|||||計這條數...當然要用到chinese reminder theorem. (8x9)y1 mod 7 = 1 y1=4 (7x9)y2 mod 8 = 1 y2=7 (7x8)y3 mod 9 = 1 y3=5 The least value = (72x4x4+63x7x5+56x5x6) mod 504 = 501|||||The LCM for 7, 8, 9 is 7 X 8 X 9 = 504, therefore the answer is 504 - (7 - 4) = 504 - (8 - 5) = 504 - (9 - 6) = 504 - 3 = 501|||||answer is 501 I found it with the help of ms excel 2007-05-10 10:33:18 補充： 雁妮 的答案好似好正確,但如果條問改為除7是會剩3不是剩4的話,佢個方法就會不成立但我卻知案案會變為213213/除7剩3213/除8剩5213/除9剩663D0B758E2D502CC
文章標籤
全站熱搜
留言列表
