|
|
Author |
abababa
Posted 2021-3-19 12:17
回复 2# isee
能分解是肯定的，但不能确定是不是最优分解。分解的话网友给讲过一个哥伦布方法，还附带了程序，程序我看不懂，但他讲的那个过程我能看懂，下面我发上来：
设$a < b$且$\gcd(a,b) = 1$，考察有理数$\frac{a}{b}$的单位分数分解。
如果$a = 1$则已经是单位分数，终止计算。
如果$a \neq 1$，因为$\gcd(a,b) = 1$，由 Bezout，方程$ax+by = 1$有整数解，不妨设其中$x > 0, y < 0$。令$a' = x, r = -y$则$aa' = br+1$，其中$a',r > 0$，易知
\[\frac{a}{b} = \frac{r}{a'}+\frac{1}{a'b}\]
其中$a' = x$是$a$关于模$b$的乘法逆元，因此$0 < a' < b$。
由$aa' = br+1 > br > ar$知$a' > r$，所以$0 < \frac{r}{a'} < 1$。由$aa' = br+1$知$\gcd(r,a') = 1$。于是$\frac{1}{a'b}$是一个单位分数，$\frac{r}{a'}$是一个新的满足条件的待分解有理数，重复此过程即可完成$\frac{a}{b}$的分解。
由于$aa' = br+1 > br > a'r$，因此$r < a$，于是每次分解都使分子减小，最终减小到$1$即为单位分数，因此算法收敛。
应用到这里的$\frac{3}{5}$（这里$a=3,b=5$），就是先求方程$3x+5y=1$的整数解，容易得到$x=2,y=-1$是一个解并且满足$x>0,y<0$，然后令$a'=x=2,r=-y=1$，就有$aa'=br+1$，也就是$3\cdot2=5\cdot1+1$，然后
\[\frac{a}{b} = \frac{r}{a'}+\frac{1}{a'b}\]
就是
\[\frac{3}{5}=\frac{1}{2}+\frac{1}{2\cdot5}=\frac{1}{2}+\frac{1}{10}\]
这时需要再继续分解$\frac{r}{a'}=\frac{1}{2}$，分子$1$小于之前的分子$3$，然后它已经是一个单位分数了，就中止了。 |
|
hbghlyj
Posted 2022-6-30 03:09
