求方程的互质解

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

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

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

Z(ω)及丢番图方程a²-ab+b²= n²简介一、Eisenstein整数环Z(ω)简介。

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

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

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

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

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

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

按照所给的参数(u, v)的定义域，这个通解公式确实可以不重复地给出所有的({a, b}, N)互质解。请特别注意这里使用无序对{a, b}的意思：公式不保证 a

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

一般说来，这个问题的提法是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 · 发表于 2010-4-7 00:34:41

提示: 该帖被管理员或版主屏蔽

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

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

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

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

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

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

好吧，我先学习下

账号		自动登录	找回密码
密码			欢迎注册

[分享] 求方程的互质解

评分