求方程的互质解
看似简单，但蕴含高深的知识如果,正整数a,b,N，满足，a^2-ab+b^2=N^2试问，1≤a<b<10^100以内的互质的解有多少组？ 大概估计一下解的数目还是容易的，但是准确求值，需要计算某个很大范围双曲线内部互素整点的数目，很难呀 2# mathe
只要找出非平凡解即可，互质应该不是难点吧 我是从N入手的，只是还没找到其递归式子，不知道有没有，
如果没有，也不知道计算机的计算能力能走多远，如果你觉得上限大了，我可以调小一点
关键是想看看能不能挖掘出很好的约束来 要求互质解的话，N有且只能有1(mod3)的质因数。这是数论中关于Z(ω)的一个基本定理。
如果我没算错的话，当N有k个1(mod3)的质因子时，a2-ab+b2=N2的互质解(a,b)对数为2k-1。
对这种计数问题，我基本不会从计算层面去考虑，只能给出数论上的结论。
不知这个结论对优化算法是否有用。 在算法上，这个问题与求本原勾股数完全相同。关于本原勾股数的两个公式
1、通解公式：a=|u2-v2|, b=2uv, c=u2+v2, 式中GCD(u, v)=1, u, v一奇一偶。
2、计数公式：c只含有1(mod4)的质约数，当c有k个1(mod4)的质约数时，本原(a,b)对有2k-1个。
LZ的问题中也有对应的通解公式和计数公式，它们对对优化算法的作用应该是完全一样的。一定范围内的勾股数应该有现成的算法吧，可以拿来参考一下。 比如当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} 再比如：
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)组。。。 我们可以有通解:
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<b,还有可能有公共的因子2需要消去 现在我们知道$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的要求