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為整數
若 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
→
11/22 23:22,
1年前
, 1F
11/22 23:22, 1F
→
11/23 02:27,
1年前
, 2F
11/23 02:27, 2F
→
11/23 02:28,
1年前
, 3F
11/23 02:28, 3F
→
11/23 02:40,
1年前
, 4F
11/23 02:40, 4F
→
11/23 02:41,
1年前
, 5F
11/23 02:41, 5F
→
11/23 03:20,
1年前
, 6F
11/23 03:20, 6F
→
11/23 03:22,
1年前
, 7F
11/23 03:22, 7F
討論串 (同標題文章)