※ 引述《baby7676 (哇哩咧)》之銘言：
: 簡單爬了一下文章沒有找到類似的問題~~
: 上來問問各位高手...
: 我在隨班上課時 無意間聽到一位學生的問題
: 問題是:
: 為什麼三個數的短除法求最小公倍數..
: 只要兩個可以除 就必須除下去???!!!
: 我頓時想了一下!我似乎找不出正確解釋@@...
: 麻煩各位高手幫我指點一下~~
以三個數來說，所謂的短除法，其實是用到下面的過程來列式
設 d 表示正整數 a, b, c 的最大公因數 (a,b,c).
則一般所謂的短除法求最小公倍數實際上分成三個步驟，
(1) 先提出三個數的最大公因數 d 使得 a = d p, b = d q, c = dr
其中 (p,q,r) = 1.
(2) 再提出任二個數的最大公因數 (p,q), (p,r), (q,r)
(3) 最後留下兩兩互質的三個數字 e, f, g
不難發現可以列出 [a,b,c] = d*(p,q)*(p,r)*(q,r)*e*f*g
其中 e = p/(p,q)(p,r), f = q/(p,q)(q,r), g = r/(p,r)(q,r)
所以 [a,b,c] = (a,b,c) abc /(a,b)(a,c)(b,c) ---(*)
而要證明 (*) 僅需對 a,b,c 的任一個質因數的指數 (設三數之指數為 x,y,z)
作排容原理, 即
min(x,y,z) = x + y + z - max(x,y) - max(x,z) - max(y,z) + min(x,y,z).
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.160.168.6
※ 編輯: armopen 來自: 1.160.168.6 (11/06 15:48)