YLL討論網

古埃及人把真分數表示成若干個分子為1的分數之和。如：3/5＝1/2＋1/10，任給一真分數，按如下步驟將它表示成若干個分子為1的分數之和。首先寫出
    m/n＝1/﹝n/m﹞＋（m/n－1/﹝n/m﹞）
若m/n－1/﹝n/m﹞＝0則停止。否則對（m/n－1/﹝n/m﹞）重複上面的步驟。證明對任意真分數m/n，按上步驟一定會在有限步驟內停止。
（註：﹝x﹞表示不小於x的最小整數。如﹝2.5﹞＝﹝3﹞＝3）

let n>1, (m,n)=1
let [n/m]+1=k
n+m>km>n
m>mk-n>=1

m/n-1/k
=(mk-n)/(nk)

m>(mk-n) ==> 分子遞減

so, 重複上面的步驟,一定會在有限步驟內become 分子=1 ==> 停止##

多謝了!