Re: [小學] 埃及古分數
※ 引述《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為整數
若n0整除b, 則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