数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 9392|回复: 44

[分享] 求方程的互质解

[复制链接]
发表于 2010-4-1 14:14:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
如果,正整数a,b,N,满足,$a^2-ab+b^2=N^2$

试问,$1≤a<b<10^100$以内的互质的解有多少组?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-1 14:40:01 | 显示全部楼层
大概估计一下解的数目还是容易的,但是准确求值,需要计算某个很大范围双曲线内部互素整点的数目,很难呀
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-4-1 15:21:35 | 显示全部楼层
2# mathe


只要找出非平凡解即可,互质应该不是难点吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-4-1 15:23:59 | 显示全部楼层
我是从N入手的,只是还没找到其递归式子,不知道有没有,
如果没有,也不知道计算机的计算能力能走多远,如果你觉得上限大了,我可以调小一点
关键是想看看能不能挖掘出很好的约束来
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-1 17:07:09 | 显示全部楼层
要求互质解的话,N有且只能有1(mod3)的质因数。这是数论中关于Z(ω)的一个基本定理。
如果我没算错的话,当N有k个1(mod3)的质因子时,a2-ab+b2=N2的互质解(a,b)对数为2k-1

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

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

评分

参与人数 1鲜花 +8 收起 理由
wayne + 8

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 08:35:56 | 显示全部楼层
在算法上,这个问题与求本原勾股数完全相同。关于本原勾股数的两个公式

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

LZ的问题中也有对应的通解公式和计数公式,它们对对优化算法的作用应该是完全一样的。一定范围内的勾股数应该有现成的算法吧,可以拿来参考一下。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-4-2 10:11:42 | 显示全部楼层
比如当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}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-4-2 10:23:54 | 显示全部楼层
再比如:
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)组。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 11:23:04 | 显示全部楼层
我们可以有通解:
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需要消去

评分

参与人数 2威望 +2 金币 +2 贡献 +2 鲜花 +10 收起 理由
wayne + 8 等周末了我也 好好推一下
hujunhua + 2 + 2 + 2 + 2 通解公式多少会有些用处吧

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 11:30:28 | 显示全部楼层
现在我们知道$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的要求
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

GMT+8, 2017-7-26 18:32 , Processed in 0.241632 second(s), 21 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表