Re: [小學] 埃及古分數

[mantour (朱子)]

※ 引述《MTGabr (暱稱可以吃嗎？)》之銘言：
: 如題，最近學到埃及古分數，是把所有的分子不為1的分數拆成很多個分子為1的異分母相加
: 。
:
: 老師講到一半就下課了，所以自己在想要怎麼拆，目前想到的算法是：
: 分母跟分子先換成最簡分數，然後擴分後，分子減1，剩下的部分可以跟原本的分母做約分
: ，重複上述步驟就可以了。
: 以下是問題：是否對每一個正整數數對（a,b），都一定存在大於1小於b的整數n使得(an-1)
: 與b不互質？
:
:

以下只考慮真分數 (a<b) , 且a>1 的情況(若a=1就不用再分解了):

令 (an-1)/b=c

因為(a,b)=1

an-bc = 1 必有整數解n0,c0 及通解

n=n0+kb, c=c0+ka , k為整數

若 mod(n0,b)=0 , 則 an0-bc 為b的倍數 不可能等於1

若 mod(n0,b)=1, 則

mod(a,b)*mod(n0,1) - mod(b,b)*mod(c,b) = 1

=> a = 1 矛盾

因此 1<mod(n0,b)<b

因此 mod(n0,b) 就是你要找的n的一個解

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.4.106 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1732286562.A.D41.html
※ 編輯: mantour (36.224.4.106 臺灣), 11/22/2024 22:45:17
→ mantour     : 這樣好像沒有保證不重複就是了
→ TimcApple   : 可以證明不重複 只要說明扣完之後分母變大就行
→ TimcApple   : 分子 2 的時候會比較難搞 但可以特事特辦
→ Ricestone   : 問題就是目前這手法沒有分母一定變大吧
→ Ricestone   : 如果貪婪法的話就很直接能看出分子單調遞減
→ Ricestone   : 目前感覺至少要能接受n為1的可能，然後每次只能選
→ Ricestone   : 最小的那個n之類的條件吧