数学研发论坛

 找回密码
 欢迎注册
12
返回列表 发新帖
楼主: kte

[求助] 怎证如下pell方程无正整数解

[复制链接]
发表于 2017-7-12 16:00:24 | 显示全部楼层
只有一组解了?程序报告所有的解都找到了?根据前面kastin的估算,应该复杂度有点偏大。
当然如果我们在加上$x^2 -= -3580 (mod 1141)$这个条件可以加速500倍左右,但是还是有点偏大
是不是$x^2-1141y^2=-1$的解要小很多?

点评

恩恩。所有解找到了。另外,=-1的无解。  发表于 2017-7-12 16:10
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-7-12 16:16:24 | 显示全部楼层
$x^2-1141y^2=-1$无整数解。
$x^2-1141y^2=1$的解满足递推公式 $T_n = 2073564788314447926474250430 T_{n-1}- T_{n-2}$,即

$x_n = 2073564788314447926474250430 x_{n-1}- x_{n-2} , x_1 = 1036782394157223963237125215,  x_2 = 2149835465668770620046057429573836642230564915177592449$
$ y_n = 2073564788314447926474250430 y_{n-1}- y_{n-2}, y_1 = 30693385322765657197397208 , y_2 = 63644723039454352911420468435537730368888828774799440$



LinearRecurrence[{2073564788314447926474250430,-1},{1036782394157223963237125215,2149835465668770620046057429573836642230564915177592449},10]
LinearRecurrence[{2073564788314447926474250430,-1},{30693385322765657197397208,63644723039454352911420468435537730368888828774799440},10]

  1. {1036782394157223963237125215,30693385322765657197397208}
  2. {2149835465668770620046057429573836642230564915177592449,63644723039454352911420468435537730368888828774799440}
  3. {4457823122280356933416781142655978994728046537252754363537864855269973556065877855,131971456656637832121231141123756847385482339109584803556899725319840790386361992}
  4. {9243585058894519638594725066571871621266187488184930250086986353675824181303432782536565833696385495883635201,273651365585770566054706421954075116143166371569506134022486705110350499624947520984208615073011804066857120}
  5. {19167172495913208283722251442629070980084768270305336286235773100065183724940371224523109354205225413047822704923947469893646793971508575,567433835952817944103159925648327643696607866567161562623238937224351658971592510044984688606333065227041177572612750876275067522199608}
  6. {39744373979074780248950565782411337526876483844674211251987446277940289001556312065452490642690532507004534336574456986621234713599927953658855487112689303558802049,1176610821929960111393558238433066211425366619183821383770285568487843088284356668989409768589341373993024247958973782577957744997125325386416442191283402572974320}
  7. {82412534416610449129798985656931113849740205760831448626754012018163549912749222635727839578000473117572106308952079140720698035353162055693115297085378814243989479202205226128115982051622495,2439778769903686322453279435775484761430937565340485534279000478504725787567443561803688884552851368894966064532462420215860991621313410875636843042300592024852847893212543621081430116757992}
复制代码


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-7-12 20:02:06 | 显示全部楼层
$x^2-dy^2=\pmQ$可以用如下算法实现求得其解

设$P^2=d (mod Q)$

连分式展开$\frac{P+\sqrt{d}}{Q}$直到其循环节$Q$的值等1,然后计算$(QA_i-PB_i)^2-dB_i^2=(-1)^{i+1}Q*Q_{i+1}$

其中$[a_0,a_1,a_2,...,a_i]=A_i/B_i$

举例$x^2-4181y^2=1117$

PowerModList[4181,1/2,1117]={93,1024}

${i,Q,P,a}$

{0,1117,1024,0}

{1,-935,-1024,1}

{2,4,89,38}

{3,53,63,2}

{4,44,43,2}

{5,49,45,2}

{6,28,53,4}

{7,25,59,4}

{8,100,41,1}

{9,7,59,17}

{10,83,60,1}

{11,44,23,1}

{12,85,21,1}

{13, 1, 64, 128}

FromContinuedFraction[{0, 1, 38, 2, 2, 2, 4, 4, 1, 17, 1, 1, 1}]=589788/605141

$(1117*589788-1024*605141)^2-4181*605141^2=-1117$

$39128812^2-4181*605141^2=-1117  (1)$

$489181478614821790^2-4181*7565365622404889^2=-1    (2)$

两式相乘,得

$(39128812*489181478614821790-4181*605141*7565365622404889)^2-4181*(39128812*7565365622404889-489181478614821790*605141)^2=1117$


$6982268099689^2-4181*107983260522^2=1117$

评分

参与人数 1威望 +3 金币 +3 贡献 +3 经验 +3 鲜花 +3 收起 理由
wayne + 3 + 3 + 3 + 3 + 3 赞一个!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-7-13 08:13:57 | 显示全部楼层
我觉得pell方程应该都可以通过穷举法找到迭代的初始解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-21 09:18:35 | 显示全部楼层
kte 发表于 2017-7-12 20:02
$x^2-dy^2=\pmQ$可以用如下算法实现求得其解

设$P^2=d (mod Q)$

请问
{i,Q,P,a}
这个是怎么计算出来的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-21 11:52:37 | 显示全部楼层
本帖最后由 mathematica 于 2019-3-21 11:57 编辑
wayne 发表于 2017-7-12 15:48
关于$ x^2-1141y^2=-3580$
$ {x,y}$ 均满足方程:$ T_n = 1275183065 T_{n-4} - T_{n-8}$,即$ x_n = 1275 ...

  1. Reduce[x^2 - 1141*y^2 == -3580 && x >= 0 && y >= 0, {x, y}, Integers]
复制代码



(x==639&&y==19)

(x==103329&&y==3059)

(x==11045193&&y==326987)

(x==1782156738&&y==52759792)

(x==816624135273&&y==24175718443)

(x==131763401968578&&y==3900784668848)

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=0&&x==1/2 (639 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-19 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+639 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+19 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1])&&y==(1/2282)(21679 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-639 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+21679 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+639 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=0&&x==1/2 (103329 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-3059 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+103329 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+3059 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1])&&y==(1/2282)(3490319 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-103329 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+3490319 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+103329 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=0&&x==1/2 (11045193 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-326987 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+11045193 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+326987 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1])&&y==(1/2282)(373092167 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-11045193 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+373092167 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+11045193 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=0&&x==891078369 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-26379896 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+891078369 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+26379896 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]&&y==(1/1141)(30099461336 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-891078369 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+30099461336 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+891078369 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=0&&x==1/2 (816624135273 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-24175718443 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+816624135273 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+24175718443 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1])&&y==(1/2282)(27584494743463 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-816624135273 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+27584494743463 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+816624135273 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=0&&x==65881700984289 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-1950392334424 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+65881700984289 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+1950392334424 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]&&y==(1/1141)(2225397653577784 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-65881700984289 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+2225397653577784 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+65881700984289 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=1&&x==1/2 (-639 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-19 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-639 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+19 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1])&&y==(1/2282)(21679 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+639 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+21679 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]-639 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=1&&x==1/2 (-103329 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-3059 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-103329 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+3059 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1])&&y==(1/2282)(3490319 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+103329 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+3490319 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]-103329 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=1&&x==1/2 (-11045193 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-326987 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-11045193 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+326987 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1])&&y==(1/2282)(373092167 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+11045193 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+373092167 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]-11045193 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=1&&x==-891078369 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-26379896 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-891078369 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+26379896 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]&&y==(1/1141)(30099461336 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+891078369 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+30099461336 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]-891078369 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=1&&x==1/2 (-816624135273 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-24175718443 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-816624135273 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+24175718443 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1])&&y==(1/2282)(27584494743463 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+816624135273 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+27584494743463 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]-816624135273 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))

(C[1]\[Element]\[DoubleStruckCapitalZ]&&C[1]>=1&&x==-65881700984289 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-1950392334424 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]-65881700984289 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]+1950392334424 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]&&y==(1/1141)(2225397653577784 (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+65881700984289 Sqrt[1141] (1036782394157223963237125215-30693385322765657197397208 Sqrt[1141])^C[1]+2225397653577784 (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]-65881700984289 Sqrt[1141] (1036782394157223963237125215+30693385322765657197397208 Sqrt[1141])^C[1]))
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-21 15:09:58 | 显示全部楼层
`11|(37-2^2)`,而 `11` 为素数,所以展开 `\frac{2+\sqrt{37}}{11}=[0,1,\overline{2,1,3}]`,循环节长度为3,比较短,因此只需要检验第三个和第五个完全商,看看分母是否为1,若不是,则原方程无解。容易检验得知,这两个完全商的分母为4和3,故原方程无解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-21 15:18:02 | 显示全部楼层
kastin 发表于 2019-3-21 15:09
`11|(37-2^2)`,而 `11` 为素数,所以展开 `\frac{2+\sqrt{37}}{11}=[0,1,\overline{2,1,3}]`,循环节长度 ...

如何计算完全商的?

点评

连分数是辗转相除得到的,每次都是得到部分商依次构成序列`[a_1,a_2,a_3,\cdots]`,第 `k` 个完全商就是除去前 `k-1` 个部分商之后剩余的序列构成的连分数的值。  发表于 2019-3-21 18:04
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-6-17 18:53 , Processed in 0.059550 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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