請問各位先進
假設有一個線段L被等分成m等份
線段L同時也被等分成n等份(m與n為正整數)
如何證明最小區間長度為:L / LCM(m,n)
LCM是指最小公倍數

高中

回應

訪客 (未驗證)

2003-07-22 23:08
應該是這樣吧

令L/m=a
L/n=b 且 a>b 所以可令 L= abr = mn/r
c mod d = e 表 "c除以d之餘數等於e"
題目所求即為 D= bk mod a (k為自然數) 之最小值
而此種運算方式與輾轉相除法是相同的,即D之最小值即為a,b之最大公因數,以(a,b)表示
另設最小公倍數,以[a,b]表示

因為(m,n)*[m,n]=mn
所以[m,n]=mn/(m,n)
L/[m,n]=(m,n)/r
=(L/a,L/b)/r
=(br,ar)/r
=(a,b) 得證

:-)