pCloud Partner Program

中國剩餘定理

數學 2013/02/25 12:22
views: 164462 times
這是個古老的數學問題, 當然也有對應的解法. 在解這個數學問題之前, 我們先來看簡單一點的題目, 就是相同餘數的數字.

舉例來說, 某數除以 7 餘 4, 除以 13 也餘 4, 則某餘最小的自然數為何?

計算方式還蠻單純的, 就是 7 和 13 的最小公倍數, 再加上 4 即得, 如下:

lcm(7,13) = 91, 由於兩數互質, 所以最小公倍數就是該兩數的乘積, 故答案則為 91 + 4 = 95

另一個變形的題目, 某數除以 7 餘 5, 除以 13 餘 11, 除以 15 餘 13, 則某數的最小自然數為何?

再看一下題目, 雖然和上面的同餘數不太一樣, 不過有個規律, 就是都差 2 就會整除, 也就是雖然餘數不一樣, 但同樣少了 2, 所以計算方式也很類似, 找出 7, 13, 15 的最小公倍數, 然後減 2就是答案了, 如下:

lcm(7, 13, 15) = 1365, 故答案為 1365 - 2 = 1363

以上兩種都是比較單純的餘數問題, 再來看看這個中國餘數定理的問題:

孫子算經中的: 有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?

換成數學白話, 某數除以 3餘 2, 除以 5餘 3, 除以 7餘 2, 某數為何?

這個既不是同樣的餘數, 也不是同樣的差某一值可整除, 要如何解呢? 這時會用到一些餘數的式子, 可以先參考這裡: http://www.mikekong.net/Maths/Problems/chinese_remainder02.html

所以只需要先找出 5, 7 的公倍數, 除以 3餘 1的; 再找出 3, 7的公倍數, 除以 5餘 1的; 再找出 3, 5的公倍數, 除以 7餘 1的, 如下:

找出 5, 7 的公倍數, 除以 3餘 1的: 5 x 7 x 2 = 70, 該數除以 3會餘 1
找出 3, 7的公倍數, 除以 5餘 1的: 3 x 7 = 21, 該數除以 5會餘 1
找出 3, 5的公倍數, 除以 7餘 1的: 3 x 5 = 15, 該數除以 7會餘 1

然後利用:
a ≡ b (mod m) 則 ac ≡ bc (mod m) 這個式子(注意反之不然), 得
70 ≡ 1 (mod 3) ... (a)
21 ≡ 1 (mod 5) ... (b)
15 ≡ 1 (mod 7) ... (c)
因為要除以 3餘 2, 所以 (a) x 2:
70 x 2 ≡ 1 x 2 (mod 3) ... (d)
因為要除以 5餘 3, 所以 (b) x 3:
21 x 3 ≡ 1 x 3 (mod 5) ... (e)
因為要除以 7餘 2, 所以 (c) x 2:
15 x 2 ≡ 1 x 2 (mod 7) ... (f)

再利用:
a ≡ b (mod m) 則 a + c ≡ (b + c) (mode m) 這個式子,
並綜合以上 (d), (e), (f) 得該數應為
x ≡ (70 x 2 + 21 x3 + 15 x 2)(mod 105)

所以最小的某數應為 23, (即 70x2 + 21x3 + 15x2 - 105x2 = 23)

相關閱讀:
http://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E4%BD%99%E6%95%B0%E5%AE%9A%E7%90%86
http://www.mikekong.net/Maths/Problems/chinese_remainder02.html
http://www.geocities.ws/goodprimes/SCCongruence.html



top

Trackback Address :: http://diary.tw/tim/trackback/1033

  1. Tracked from warming trends crossfire burner 2017/12/02 04:27 DELETE

    Subject: warming trends crossfire burner

    Find top Fire pit natural gas burner currently available in addition on sale now!
  2. Tracked from Harter 2017/12/02 10:06 DELETE

    Subject: Harter

    Find here top Hand painted wallpaper that are available and on sale today!
  3. Tracked from custom wallpaper 2017/12/04 19:04 DELETE

    Subject: custom wallpaper

    Find here professional paul montgomery wallpaper currently now in stock plus at great prices today!
  4. Tracked from how much yerba mate per cup 2017/12/06 22:40 DELETE

    Subject: how much yerba mate per cup

    Get most popular mate tea cup that's available in addition currently available. Get it today!
  5. Tracked from Harter 2017/12/08 17:07 DELETE

    Subject: Harter

    Find the best famous art wallpapers that are now in stock plus at the best price today!
  6. Tracked from yerba mate vs coffee 2017/12/09 21:05 DELETE

    Subject: yerba mate vs coffee

    See top quality brewing yerba mate currently available plus currently available. Get it today!
  7. Tracked from help with importing from china 2017/12/11 02:25 DELETE

    Subject: help with importing from china

    Find the best china sourcing solutions currently available plus at great prices today!

Write a comment


PREV : [1] : ... [129] : [130] : [131] : [132] : [133] : [134] : [135] : [136] : [137] : ... [473] : NEXT



Nextbit Robin 5.2吋六核心智慧型手機 Microsoft Office 365 中文家用版PKC (無光碟)
ASUS華碩 AC1900 雙頻無線路由器 RT-AC68U 美國 VORNADO 533 渦流空氣循環機 (黑色)
御茶園 每朝健康綠茶(650mlx24入) 每朝健康 雙纖綠茶(650mlx24入)


 Waiting...