数学研发论坛

标题: 求方程的互质解 [打印本页]

作者: wayne 时间: 2010-4-1 14:14
标题: 求方程的互质解
[jh]看似简单，但蕴含高深的知识[/jh]如果,正整数a,b,N，满足，[TeX]a^2-ab+b^2=N^2[/TeX]

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

作者: mathe 时间: 2010-4-1 14:40
大概估计一下解的数目还是容易的，但是准确求值，需要计算某个很大范围双曲线内部互素整点的数目，很难呀

作者: wayne 时间: 2010-4-1 15:21
2# mathe

只要找出非平凡解即可，互质应该不是难点吧

作者: wayne 时间: 2010-4-1 15:23
我是从N入手的，只是还没找到其递归式子，不知道有没有，
如果没有，也不知道计算机的计算能力能走多远，如果你觉得上限大了，我可以调小一点
关键是想看看能不能挖掘出很好的约束来

作者: hujunhua 时间: 2010-4-1 17:07
要求互质解的话，N有且只能有1(mod3)的质因数。这是数论中关于Z(ω)的一个基本定理。
如果我没算错的话，当N有k个1(mod3)的质因子时，a[sup]2[/sup]-ab+b[sup]2[/sup]=N[sup]2[/sup]的互质解(a,b)对数为2[sup]k-1[/sup]。

对这种计数问题，我基本不会从计算层面去考虑，只能给出数论上的结论。

不知这个结论对优化算法是否有用。

作者: hujunhua 时间: 2010-4-2 08:35
在算法上，这个问题与求本原勾股数完全相同。关于本原勾股数的两个公式

1、通解公式：a=|u[sup]2[/sup]-v[sup]2[/sup]|, b=2uv, c=u[sup]2[/sup]+v[sup]2[/sup], 式中GCD(u, v)=1, u, v一奇一偶。
2、计数公式：c只含有1(mod4)的质约数，当c有k个1(mod4)的质约数时，本原(a,b)对有2[sup]k-1[/sup]个。

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

作者: wayne 时间: 2010-4-2 10:11
比如当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 时间: 2010-4-2 10:23
再比如：
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 时间: 2010-4-2 11:23
我们可以有通解:
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 时间: 2010-4-2 11:30
现在我们知道$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的要求

作者: mathe 时间: 2010-4-2 11:35
看 http://mathworld.wolfram.com/LegendreSymbol.html
有
$(-3/p)=1$当且仅当$p-=1(mod 6)$
由此我们得到N的素因子必然是2,3或模6为1的素数

作者: mathe 时间: 2010-4-2 11:46

再比如：
N=7时，解为{2,3}
N=7^2，解为{3,8}
N=13^100，解为{9775102200283600508421924434475532688916648626365699376,53955571680724430555006954675322605232760286996653695375}

N=7*13时，解为{1, 10},
wayne 发表于 2010-4-2 10:23

只要证明对于每个素数p，其中p模6为1，
那么$p=u^2+3v^2$的分解方案存在而且唯一就可以了

作者: mathe 时间: 2010-4-2 11:47
是不是$Z(\omega)$是唯一因子分解整环？

作者: hujunhua 时间: 2010-4-2 11:56
Y. 1(mod6)的素数具有唯一分解u[sup]2[/sup]+3v[sup]2[/sup]，分解成a+bω和a+bω[sup]2[/sup]，是z(ω)中的素数。

作者: mathe 时间: 2010-4-2 12:39
http://mathworld.wolfram.com/EisensteinInteger.html

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

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

作者: hujunhua 时间: 2010-4-2 17:02
wayne在线啊？这花献的够快，我想改帖缩头都来不及了。看来得辛苦一点码公式了。

作者: wayne 时间: 2010-4-2 17:13
呵呵，先让我自己来吧，
我明天贴出我的推导来
然后还要你来纠正。。。

作者: wayne 时间: 2010-4-3 22:09

{a, b}={u[sup]2[/sup]-v[sup]2[/sup], 2uv-v[sup]2[/sup]}
N=u[sup]2[/sup]-uv+v[sup]2[/sup]
u>v>0, Gcd(u,v)=1, u≠-v(mod3)

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

太不可思议了！！！

作者: wayne 时间: 2010-4-3 22:17
emath里的又一个神人啊，
快快贴出过程吧

作者: wayne 时间: 2010-4-3 22:40
9# mathe

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

作者: hujunhua 时间: 2010-4-4 01:42
Z(ω)及丢番图方程a[sup]2[/sup]-ab+b[sup]2[/sup]= n[sup]2[/sup]简介

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

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

三、丢番图方程a[sup]2[/sup]+ab+b[sup]2[/sup]= n[sup]2[/sup]的通解公式和解数

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

作者: 只是呼吸 时间: 2010-4-4 22:40
40# hujunhua

就是要看看隐藏了什么

作者: hujunhua 时间: 2010-4-6 00:16

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

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

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

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

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

作者: hujunhua 时间: 2010-4-7 00:34
提示: 该帖被管理员或版主屏蔽

作者: hujunhua 时间: 2010-4-7 16:03

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

Mathe的公式略有问题，要做通解公式需要做些处理。
(, 下载次数: 0)

作者: wayne 时间: 2010-4-7 17:09
神奇~~
原来二者之间是这样等效的，
我原先推导了一会，
没发现等效性就放弃了

作者: 282842712474 时间: 2011-7-28 20:33
好吧，我先学习下

作者: cn8888 时间: 2014-7-1 18:46
回复看答案

作者: kastin 时间: 2014-7-2 14:48
高斯整数分解跟这个也差不多

作者: sunwukong 时间: 2014-7-18 17:08
回复，为了学习

作者: dianyancao 时间: 2014-7-25 00:47
have a see

作者: ccmmjj 时间: 2015-5-12 01:50
看看

作者: plzhtar 时间: 2016-8-2 13:01
两种同余式是互含的怎么理解

作者: plzhtar 时间: 2016-8-2 14:54
2(mod3)的自然素数，即2和6m-1形自然素数在Z(ω)仍然是素数。这个怎么理解

作者: plzhtar 时间: 2016-8-2 15:35
这部分内容好像抽代中没有作为例子引入，能推荐本这方面的书吗

作者: plzhtar 时间: 2016-8-2 17:12
当ρ不整除a+bω时，Gcd(a+bω, a+bω')=Gcd(a, b). 这是怎么推的？

作者: manthanein 时间: 2017-1-24 17:10
回复

作者: 王守恩 时间: 2019-3-15 06:26
宝库开门！

作者: 白新岭 时间: 2019-3-16 13:35
主贴中的N应没有平方数字2

作者: xiaoshuchong 时间: 2022-4-11 12:50
回复，看答案

欢迎光临数学研发论坛 (https://bbs.emath.ac.cn/)