求方程的互质解

wayne

如果,正整数a,b,N，满足，$a^2-ab+b^2=N^2$ 试问，$1≤a

mathe

大概估计一下解的数目还是容易的，但是准确求值，需要计算某个很大范围双曲线内部互素整点的数目，很难呀

wayne

2# mathe 只要找出非平凡解即可，互质应该不是难点吧

wayne

我是从N入手的，只是还没找到其递归式子，不知道有没有， 如果没有，也不知道计算机的计算能力能走多远，如果你觉得上限大了，我可以调小一点 关键是想看看能不能挖掘出很好的约束来

hujunhua

要求互质解的话，N有且只能有1(mod3)的质因数。这是数论中关于Z(ω)的一个基本定理。 如果我没算错的话，当N有k个1(mod3)的质因子时，a²-ab+b²=N²的互质解(a,b)对数为2^k-1。 对这种计数问题，我基本不会从计算层面去考虑，只能给出数论上的结论。 不知这个结论对优化算法是否有用。

hujunhua

在算法上，这个问题与求本原勾股数完全相同。关于本原勾股数的两个公式 1、通解公式：a=|u²-v²|, b=2uv, c=u²+v², 式中GCD(u, v)=1, u, v一奇一偶。 2、计数公式：c只含有1(mod4)的质约数，当c有k个1(mod4)的质约数时，本原(a,b)对有2^k-1个。 LZ的问题中也有对应的通解公式和计数公式，它们对对优化算法的作用应该是完全一样的。一定范围内的勾股数应该有现成的算法吧，可以拿来参考一下。

wayne

比如当N=7*13*19*31*37*43 其解有2^5=32组，如下： {a,b}: {5, 9237}, {157, 9312}, {368, 9413}, {873, 9640}, {880, 9643}, {960, 9677}, {1063, 9720}, {1383, 9848}, {1565, 9917}, {1592, 9927}, {1752, 9985}, {1933, 10048}, {2277, 10160}, {2435, 10208}, {2640, 10267}, {2687, 10280}, {2787, 10307}, {3127, 10392}, {3272, 10425}, {3355, 10443}, {3625, 10497}, {3707, 10512}, {3953, 10553}, {4103, 10575}, {4177, 10585}, {4272, 10597}, {4297, 10600}, {4755, 10643}, {4833, 10648}, {4925, 10653}, {4968, 10655}, {5295, 10663}

wayne

再比如： N=7时， 解为{2,3} N=7^2，解为{3,8} N=13^100，解为{9775102200283600508421924434475532688916648626365699376,53955571680724430555006954675322605232760286996653695375} N=7*13时，解为{1, 10}, {5, 11} ........ 总之，N的素因子个数为k,解就有 2^(k-1)组。。。

mathe

我们可以有通解: i)$(u,v)=1$, ${(b=4uv),(a=3u^2-v^2+2uv),(N=3u^2+v^2):}$ ii)$(u,v)=1$, ${(b=4uv),(a=u^2-3v^2+2uv),(N=u^2+3v^2):}$ 当然我们还需要限定条件1≤a

mathe

现在我们知道$N=u^2+3v^2$或$N={u^2+3v^2}/4$(决定于u,v是否同是奇数) 假设N有一个奇素因子p>3,那么我们知道$u^2+3v^2-=0(mod p)$,也就是$-3=(u/v)^2(mod p)$ 就是说-3是p的二次剩余,由这个可以得出对p的要求