作者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/cn.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