求方程的互质解

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的问题中也有对应的通解公式和计数公式，它们对对优化算法的作用应该是完全一样的。一定范围内的勾股数应该有现成的算法吧，可以拿来参考一下。

hujunhua

Y.  1(mod6)的素数具有唯一分解u²+3v²，分解成a+bω和a+bω²，是z(ω)中的素数。

hujunhua

mathe 劳苦，导出了通解公式。通解公式对优化算法有帮助吗，有的话我就交代一下，是从z(ω)中得来的。与mathe 的公式在形式上有所不同。
{a, b}={u²-v², 2uv-v²}
N=u²-uv+v²
u>v>0, Gcd(u,v)=1, u≠-v(mod3)。

看mathe小心翼翼的，似乎对 N 不含因子2或者3还抱有疑虑。如果你们有兴趣的话，周末了，有点空，我可以给出N只含1(mod6)的质因子、计数公式和通项公式的推导过程，蛮经典的。不过对优化算法未必有帮助。

hujunhua

wayne在线啊？这花献的够快，我想改帖缩头都来不及了。看来得辛苦一点码公式了。

hujunhua

        Z(ω)及丢番图方程a²-ab+b²= n²简介

一、Eisenstein整数环Z(ω)简介。

游客，如果您要查看本帖隐藏内容请回复

二、几个对本帖有用的引理。

游客，如果您要查看本帖隐藏内容请回复

三、丢番图方程a²+ab+b²= n²的通解公式和解数

游客，如果您要查看本帖隐藏内容请回复

hujunhua

看完之后，就会感觉没啥神的。的确如此，熟悉$Z(\omega)$的人，得到那个通项公式和计数公式不过是一闪念的事。倒是跟不熟悉的人写起来，要费不少功夫码公式。

hujunhua

我根据你给的通解公式瞬间产生了前一万组解。同我以前的排序后的解进行对比，发现每一项都是严格的对应着的！！！

太不可思议了！！！
wayne 发表于 2010-4-3 22:09

按照所给的参数(u, v)的定义域，这个通解公式确实可以不重复地给出所有的({a, b}, N)互质解。请特别注意这里使用无序对{a, b}的意思：公式不保证 a<b, 但是保证不会给出对称重复解，即不会有两对不同的参数，一个给出(a, b), 另一个给出(b, a). 这点在Z(ω)中容易证明，但在Z中稍费周折。

hujunhua

一般说来，这个问题的提法是a*b=c²在c≤N内有多少本原解。a*b=c²是Z(ω)平面上中心在原点、半径为c的圆（范数的几何意义）。
所以问题就是要计算这个圆内有多少模为正整数的整点位于第一区，要求分量坐标互质。
从通解公式中c=u*v知，问题收缩到了半径为$\sqrt{N}$ 的圆内，要求圆内在第1区内Gcd(u,v)=1并且u≠-v(mod 3)的整点数（一半）。

我现在有点明白了，对于设计算法有重要意义的是通项公式，那个计数公式用处不大。基于计数公式的算法涉及因子分解和素数表，效率肯定不会高。