找回密码
 欢迎注册
楼主: wayne

[分享] 求方程的互质解

  [复制链接]
发表于 2010-4-2 11:56:44 | 显示全部楼层
Y.  1(mod6)的素数具有唯一分解u2+3v2,分解成a+bω和a+bω2,是z(ω)中的素数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 11:47:10 | 显示全部楼层
是不是$Z(\omega)$是唯一因子分解整环?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 11:46:15 | 显示全部楼层
再比如:
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$的分解方案存在而且唯一就可以了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-4-2 11:35:01 | 显示全部楼层
http://mathworld.wolfram.com/LegendreSymbol.html

$(-3/p)=1$当且仅当$p-=1(mod 6)$
由此我们得到N的素因子必然是2,3或模6为1的素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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的要求
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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 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 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}

点评

譬如:5^2+9237^2-5*9237=85276009=7*13*19*31*37*43  发表于 2019-3-16 11:24
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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-1 17:07:09 | 显示全部楼层
要求互质解的话,N有且只能有1(mod3)的质因数。这是数论中关于Z(ω)的一个基本定理。
如果我没算错的话,当N有k个1(mod3)的质因子时,a2-ab+b2=N2的互质解(a,b)对数为2k-1

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

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

评分

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

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-5-1 19:07 , Processed in 0.045085 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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