作者mantour (朱子)
看板Math
標題Re: [小學] 埃及古分數
時間Fri Nov 22 22:42:40 2024
※ 引述《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://webptt.com/m.aspx?n=bbs/Math/M.1732286562.A.D41.html
※ 編輯: mantour (36.224.4.106 臺灣), 11/22/2024 22:45:17
1F：→ mantour : 這樣好像沒有保證不重複就是了 11/22 23:22
2F：→ TimcApple : 可以證明不重複 只要說明扣完之後分母變大就行 11/23 02:27
3F：→ TimcApple : 分子 2 的時候會比較難搞 但可以特事特辦 11/23 02:28
4F：→ Ricestone : 問題就是目前這手法沒有分母一定變大吧 11/23 02:40
5F：→ Ricestone : 如果貪婪法的話就很直接能看出分子單調遞減 11/23 02:41
6F：→ Ricestone : 目前感覺至少要能接受n為1的可能，然後每次只能選 11/23 03:20
7F：→ Ricestone : 最小的那個n之類的條件吧 11/23 03:22