求方程的互质解

wayne

9# mathe


我相信mathe给的通解如果补全了约束条件，通过某种参数转换，与hujunhua的一定等效

hujunhua

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

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

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

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

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

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

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

hujunhua

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

只是呼吸

40# hujunhua


就是要看看隐藏了什么

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)的整点数（一半）。

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

hujunhua

9# mathe
我相信mathe给的通解如果补全了约束条件，通过某种参数转换，与hujunhua的一定等效
wayne 发表于 2010-4-3 22:40

Mathe的公式略有问题，要做通解公式需要做些处理。

wayne

神奇~~
原来二者之间是这样等效的，
我原先推导了一会，
没发现等效性就放弃了

282842712474

好吧，我先学习下