不定方程求解abcd问题

袁哥哥

不定方程求解
http://weibo.com/1277439255/yoJ1j9AP0

提一个简单的数学难题，我称之为abcd问题。考虑正整数n=(a+b)（c+d)，其中a,b,c,d为正有理数，满足abcd=1。问对哪些n，有解或无解，且在有解时给出解。显然n=1,2,3无解，4=(1+1)(1+1)，5=(1+1)(2+1/2)。我们已求得，存在无穷多个n有解，无穷多个n无解，但仍存在无穷多个n无法确定是否有解，比如n=8,9。

sunwukong

4=(1+1)(1+1)
5=(1+1)(2+1/2)
6 无解
7 无解
8 无解
9 无解
10 无解
11 无解
12 无解

mathe

变换一下，可以写成
n=ac+1/(ac)+ad+1/(ad)
记s=ac,t=ad,于是
n=s+1/s+t+1/t
反之，如果存在有理数s,t使得n=s+1/s+t+1/t,那么我们总可以选择a=1,c=s,d=t,b=1/(st)满足条件。
设s=u/v, t=w/z,其中u,v,w,z是正整数,(u,v)=1,(w,z)=1,得出
n=(u^2+v^2)/(uv)+(w^2+z^2)/(wz)
于是容易证明uv=wz.
然后分别记(u,w),(u,z)为u1,u2,(v,w),(v,z)为v1,v2得出
n=(u1^2u2^2+v1^2v2^2+u1^2v1^2+u2v2^2)/(u1u2v1v2)
即
n=(u1^2+v1^2)(u2^2+v2^2)/(u1u2v1v2)
而且其中u1v1|u2^2+v2^2, u2v2|u1^2+v1^2
有这里显然可以得出的一个结论是n的所有奇素因子必须模4余1

sunwukong

问题：
n 为正整数，a、b、c、d 为正有理数，满足
abcd=1
(a+b)(c+d)=1
问对哪些n，方程有解或无解，且在有解时给出解。
显然n=1,2,3无解，4=(1+1)(1+1)，5=(1+1)(2+1/2)。
我们已求得，存在无穷多个n有解，无穷多个n无解，但仍存在无穷多个n无法确定是否有解，比如n=8,9。
不完全解答：
因为abcd=1所以sqrt{abcd}=1
所以
n=(a+b)(c+d)
=(a/sqrt{ab}+b/sqrt{ab})(c/sqrt{cd}+d/sqrt{cd})
>=2sqrt{ a/sqrt{ab}*b/sqrt{ab}}*2sqrt{ c/sqrt{cd}*d/sqrt{cd}}
  >=4
所以，当 n<4 时，原方程无解
因为
(a+b)(c+d)=(1+b/a)(ac+ad)
且
1*(b/a)*ac*ad=abcd
所以，当 {a、b、c、d} 是原方程的解时，{1、b/a、ac、ad} 也是原方程的解。不失一般性，我们可以假定 a=1。
此时
n=(1+b)(c+d)=(1+b)(c+1/(bc))
(1+b)c^2-nc+(1+b)/b=0
由一元二次方程求根公式，
c=[(n/2)±sqrt{n^2/4-(1+b)^2/b}]/(1+b)
因为 c 是正有理数，所以
n^2/4-(1+b)^2/b 是某个有理数的平方。
设 b=kx^2/y^2 ，k、x、y 是正整数，k 无平方因子，x，y互素，则
n^2/4-(1+b)^2/b=[(nkxy)^2-4k(kx^2+y^2)^2]/(2kxy)^2
所以 A=(nkxy)^2-4k(kx^2+y^2)^2 是完全平方数
以下证明 k=1
(1)当 k>1，且 k 是奇数时
   A=k[k(nxy)^2-4(kx^2+y^2)^2]
  由k无平方因子，得k(nxy)^2-4(kx^2+y^2)^2 是 k 的倍数，
  所以y是k的倍数，令y=kY，代入，得
  A=k^3[k(nxY)^2-4(x^2+ kY ^2)^2]
所以 k(nxY)^2-4(x^2+ kY ^2)^2是 k 的倍数，
所以 x 是 k 的倍数，与 x，y互素矛盾。
(2)当 k 是大于2的偶数时，令 k=2K，因为 k 无平方因子，所以 K 为奇数，K>1，且无平方因子，代入，得
A=4K [K (nxy)^2-2(2K x^2+y^2)^2]
所以，K (nxy)^2-2(2K x^2+y^2)^2 是K的倍数。
所以，y 是 K的倍数，令 y=KY，代入，得
A=4K^3 [K (nx Y)^2-2(2 x^2+ K Y ^2)^2]，
所以，K (nx Y)^2-2(2 x^2+ K Y ^2)^2 是 K 的倍数
所以，x 是 K 的倍数，与 x、y 互素矛盾。
(3) 当 k=2 时，
A=4 [ (nxy)^2-2(2 x^2+y^2)^2]
所以，A/4= (nxy)^2-2(2 x^2+y^2)^2 是完全平方数。
1^2=3^2=5^2=7^2=1 (mod 8)，2^2=6^2=4(mod 8)，0^2=4^2=0(mod 8)
(3.1)当 y 是奇数时，
2x^2+y^2 是奇数，(2 x^2+y^2)^2=1(mod 8)
2(2 x^2+y^2)^2=2=-6(mod 8)，
A/4= (nxy)^2-2(2 x^2+y^2)^2=0+6或1+6或4-2=6或7或2(mod 8)
不可能是完全平方数，矛盾。
(3.2)当 y 是偶数时，令 y=2Y，代入
A/4=4(nxY)^2-8( x^2+2Y ^2)^2，所以
A/16=(nxY)^2-2( x^2+2Y ^2)^2 是完全平方数。
由(3.1)的结论，当x 是奇数时，(nxY)^2-2( x^2+2Y ^2)^2不是完全平方数。所以 x 为偶数。与 x、y 互素矛盾。
由(1)、(2)、(3)的结论，当k>1时，原方程无解，所以 b=x^2/y^2，即 b 为某个有理数的平方，因为 bcd=1，所以 sqrt{bcd}=1，
1/sqrt{cd}=sqrt{b}/sqrt{bcd}=sqrt{b}=x/y，
c/sqrt{cd}=cx/y 为有理数，所以，可设c/sqrt{cd}=s/t，s、t为正整数，(s，t)=1
则 d/sqrt{cd}=t/s
n=(1+b)(c+d)=(1/ sqrt{b}+ sqrt{b})( c/sqrt{cd}+d/sqrt{cd})
=(x/y+y/x)(s/t+t/s)
所以原方程可化为 (x^2+y^2)(s^2+t^2)=nxyst
x、y、s、t 为正整数，x、y互素，s、t 互素
所以 x、y 为一奇一偶，或者为两奇
     s、t 为一奇一偶，或者为两奇
(4.1)当x、y 为一奇一偶，s、t 为一奇一偶时
x^2+y^2 为奇数，s^2+t^2 为奇数，nxyst 为偶数，矛盾，所以，x、y、s、t 至多有一个数是偶数。
(4.2)当 x、y、s、t 为奇数时，x^2+y^2=s^2+t^2=2 (mod 8)
nxyst =(x^2+y^2)(s^2+t^2)= 4 (mod 8)
所以 nxyst*xyst=4*xyst(mod 8)
即 n=4(mod 8)
(4.3)当 x、y、s、t 为一偶三奇时，不妨设 x 为偶数
x^2+y^2=1或5 (mod 8)，s^2+t^2=2 (mod 8)
nxyst =(x^2+y^2)(s^2+t^2)= 2 (mod 8)
nxyst*yst=2*yst (mod 8)
即 nx=±2(mod 8)
nx=8f±2，其中 f 为整数，
因为 x 为偶数，所以 x/2 为整数
所以 n(x/2)=4f±1
因为 4f±1 为奇数，所以 n、x/2 都为奇数，即
n 为奇数，x=2(mod 4)
由  (x^2+y^2)(s^2+t^2)=nxyst，x、y互素，s、t 互素
得  x^2+y^2 与 xy 互素，s^2+t^2 与 st 互素，所以，原方程可化为
x^2+y^2=n_1st
s^2+t^2=n_2xy
其中，n_1、n_2 为正整数，n_1*n_2=n ，不妨假设 n_1>=n_2
(5.1)当n为奇数时，由雅可比符号
(-1/n)=1, iif  n=1(mod 4);  
(-1/n)=-1,  iif  n=-1(mod 4)
所以，当n=-1(mod 4) 时，x^2+y^2=nxy 无解。
(5.1.1) n_1=n，n_2=1,此时x^2+y^2=nst 无解；
(5.1.2) n_1>=n_2>=3 ，且n_1、n_2之中 一个=1(mod 4)，另外一个=-1(mod 4)，总有一个方程无解；
由此可得结论：
当 n=-1(mod 4)时，原方程组无解。
但当 n=1(mod 4) 时，原方程不一定有解。
比如 ，n=9 时，原方程可化为
x^2+y^2=3st，
s^2+t^2=3xy 这两个方程都无解
或者化为
x^2+y^2=9st，
s^2+t^2=xy，
因为
1^2=1(mod 9)，2^2=4(mod 9)，3^2=0(mod 9)，4^2=7(mod 9)
所以，x^2+y^2=9st 无解.
即n=9时，原方程无解。
(5.2)当 n 为偶数时，由 n=4(mod 8)，得 n=4*N，N为奇数，因为 x、y、s、t 为奇数，x^2+y^2=s^2+t^2=2 (mod 8)
原方程可化为
x^2+y^2=2N_1st
s^2+t^2=2N_2xy
其中 N_1、N_2为奇数， N_1*N_2=N

目前得到的结论：
当n<4时，原方程无解。
当 n=0,2,3,6,7(mod 8)时，原方程无解。
n=9 时，原方程无解。
原方程可化为整数方程：
(x^2+y^2)(s^2+t^2)=nxyst
x、y、s、t 为正整数，x、y互素，s、t 互素

或者化为方程组：
x^2+y^2=n_1*s*t
s^2+t^2=n_2*x*y
其中，n_1、n_2 为正整数，n_1*n_2=n 。
当n为奇数时，n_1=n_2=1(mod 4)
当n为偶数时，n_1=n_2=2(mod 4)

注：参考资料 http://www.doc88.com/p-186619955350.html 数论算法讲义 4章（二次同余方程与平方剩余）

袁哥哥

3# mathe


一看就知道mathe的功力很深厚呀。

原题转换后等效于  (A^2+B^2)(C^2+D^2)=n*ABCD的非平凡正整数解。

n必须是平方和的乘积，所以不能有（4k+3)的素因子。

B=D=1的特殊情况可以得到通解公式。不知道所有情况能不能用佩尔方程解决？

一些程序搜索结果：
http://hi.baidu.com/yuange1975/item/e96e56126206bcfbdceeca5b

4=(1*1+1*1)*(1*1+1*1)/(1*1*1*1)

5=(2*2+1*1)*(2*2+1*1)/(2*1*2*1)

from 2 to 1527074

13.000000=(5/1+1/5)*(2/1+1/2)

68.000000=(13/1+1/13)*(5/1+1/5)

445.000000=(34/1+1/34)*(13/1+1/13)

3029.000000=(89/1+1/89)*(34/1+1/34)

1237.000000=(145/2+2/145)*(17/1+1/17)

580.000000=(157/1+1/157)*(17/5+5/17)

1156.000000=(205/13+13/205)*(73/1+1/73)

20740.000000=(233/1+1/233)*(89/1+1/89)

13621.000000=(241/1+1/241)*(113/2+2/113)

2525.000000=(293/1+1/293)*(17/2+2/17)

6925.000000=(337/1+1/337)*(41/2+2/41)

3893.000000=(533/10+10/533)*(73/1+1/73)

142133.000000=(610/1+1/610)*(233/1+1/233)

5252.000000=(697/1+1/697)*(37/5+5/37)

3893.000000=(905/1+1/905)*(442/109+109/442)

18500.000000=(1157/1+1/1157)*(653/41+41/653)

13.000000=(1285/881+881/1285)*(1049/178+178/1049)


注意A、B、C、D都必须是平方和，采用平方和数列搜索，搜索速度可以大为提高。