任意真分数拆为两个埃及分数之和

wayne

灵感源自数学星空的主题关于单位分数的一些难题，呵呵，这个肯定要简单多了

对于给定的正整数p,q，求方程的正整数解，
$\frac{1}{x}+\frac{1}{y}=\frac{q}{p}$

(即什么情况下方程有解，此时的解又是怎么构造的？)


感觉这题挺有趣的，特单独作为一个主题列出来，大家讨论讨论。

hujunhua

只需要讨论1<q<p, GCD(p, q)=1 的情况。
这个问题在数论教材里几乎有现成的答案。有解的条件是 p 存在互质双因子分解a*b, 碰巧使得q|(a+b).
x=(p+a^2)/q,  y=(p+b^2)/q

q=1, 2时恒有解。
q=3，4，6，8，12时，充要条件是q|(p+1)

wayne

2# hujunhua

也就是说，你对p每分解一次，都要进行一次 q|(a+b)的判断？

另外，一定得要互质分解吗

hujunhua

对了，忘了交代一件事：我说的是GCD(x,y,p)=1的解。
如果不限于GCD(x,y,p)=1，只要p存在两个互质的因子a和b，使得q|(a+b)就行。

参见数论教材上关于解丢番图方程1/x+1/y=1/z的部分。

hujunhua

这是一篇中学老师关于此问题的论文。刚下到的。
[local]1[/local]

wayne

呵呵，我的跟你有一点不同，仔细分析起来其实是等效的：

方程$\frac{1}{x}+\frac{1}{y}=\frac{q}{p}$的所有正整数解:
$(x,y)=(\frac{a+p}{q},\frac{b+p}{q})$,其中$a*b=p^2,a+p=0 \mod(q)$。

如果a+p模q余-p,那么，一定能保证b+p也是模q余-p的，有了这个编程序就比较方便了

wayne

不管p,q多大，都能非常快的得到所有解。

比如$\frac{1}{x}+\frac{1}{y}=\frac{211}{1448888888888868}$

1. q = 211; p = 1448888888888868; Cases[Transpose[{t = Divisors[p^2]; tt = (Length[t] - 1)/2; t[[1 ;; tt]], Reverse[t][[1 ;; tt]]}], x_ /; Divisible[x[[1]] + p, q] -> (x + p)/q]

复制代码

〇〇

7# wayne


nice code

winxos

6# wayne
其中当$q=1$时，
$1/x+1/y=1/p$的解为
$(x,y)=(a+p,b+p)$
其中$a*b=p^2$
-------------
学习了。

manthanein

hujunhua 发表于 2010-1-16 02:57
只需要讨论1

\(\D \frac{1}{9}+\frac{1}{45}=\frac{2}{15}\) 似乎不能这么拆