不定方程求解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都必须是平方和，采用平方和数列搜索，搜索速度可以大为提高。