论坛 › 难题征解 › 求方程的互质解

wayne 发表于 2010-4-3 22:40:39

9# mathe


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

hujunhua 发表于 2010-4-4 01:42:54

      Z(ω)及丢番图方程a2-ab+b2= n2简介

一、Eisenstein整数环Z(ω)简介。
**** Hidden Message *****
二、几个对本帖有用的引理。
**** Hidden Message *****
三、丢番图方程a2+ab+b2= n2的通解公式和解数
**** Hidden Message *****

hujunhua 发表于 2010-4-4 02:32:12

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

只是呼吸 发表于 2010-4-4 22:40:23

40# hujunhua


就是要看看隐藏了什么

hujunhua 发表于 2010-4-6 00:16:12

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

太不可思议了！！！
wayne 发表于 2010-4-3 22:09 http://bbs.emath.ac.cn/images/common/back.gif

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

hujunhua 发表于 2010-4-6 01:12:17

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

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

hujunhua 发表于 2010-4-7 00:34:41

hujunhua 发表于 2010-4-7 16:03:19

9# mathe
我相信mathe给的通解如果补全了约束条件，通过某种参数转换，与hujunhua的一定等效
wayne 发表于 2010-4-3 22:40 http://bbs.emath.ac.cn/images/common/back.gif
Mathe的公式略有问题，要做通解公式需要做些处理。

wayne 发表于 2010-4-7 17:09:53

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

282842712474 发表于 2011-7-28 20:33:24

好吧，我先学习下

查看完整版本: 求方程的互质解