求方程的互质解

wayne

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

试问，$1≤a<b<10^100$以内的互质的解有多少组？

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<b,还有可能有公共的因子2需要消去

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的要求