关于Pell方程及其求解技巧

傷城~ 2022-07-15 10:18 310阅读 0赞

Pell方程在不定方程里经常出现，解其他方程的时候最后往往归结为对某个pell方程的讨论。本文不加证明的叙述几个pell方程的结论，并讨论怎么用连分数来具体算出特定pell方程的解。

Pell方程，一般是指x^2-dy^2=1.①

定理1：设d是一个正整数且不是一个完全平方，则方程①有无穷多组整数解x,y.设a^2-db^2=1,a>0,b>0,是所有x>0,y>0的解中使x+y√d最小的那组解（称(a,b)为①的基本解），则①的全部解x,y,由x+y√d=±(a+b√d)^n表出，其中n是任意整数。

定理2：设u,v是正整数，满足①，且有u>v^2/2-1,则u+v√d是①的基本解。  
形如x^2-dy^2=-1②的方程也叫pell方程，显然d=4k或d含有形如4k+3的素因子时，②无解。

定理3：设d是一个正整数且不是一个完全平方，如果②有解，且设a^2-db^2=-1,a>0,b>0,是所有x>0,y>0的解中使x+y√d最小的那组解（称(a,b)为②的基本解），则②的全部解（有无穷多组）x,y,由x+y√d=±(a+b√d)^(2n+1)表出，其中n是任意整数。且(a+b√d)^2是①的基本解。

定理4：设p=1(mod 4)是素数，则x^2-py^2=-1有整数解x,y.

定理5：设p是一个素数，2p=r^2+s^2,r=±3(mod 8),s=±3(mod 8),则x^2-2py^2=-1无解。

现在来看方程x^2-dy^2=c,③其中d>0不是一个平方数，c≠0是整数。  
设x=u,y=v是③的一组解，记做u+v√d是③的一个解。显然u-v√d也是③的一个解。  
再设s+t√d是①的一个解，显然(u+v√d)(s+t√d)也是③的一个解。  
  
现在来考虑最一般的二元二次不定方程：ax^2+bxy+cy^2+dx+ey+f=0④

定理6：如果D=b^2-4ac>0,D不是一个平方数，△=4acf+bde-ae^2-cd^2-fb^2≠0，  
④有一组解，则④有无穷多组整数解。

现在介绍连分数，记\[a,b,c……,d\]=a+1/(b+1/(c……+1/d)),即  
![20161220121950143][]  
  
称为有限连分数。如果有无穷数列\{an\},bn=\[a1,a2,……,an\],且A=lim(n→∞)bn存在，那么就说\[a1,a2,……,an,……\]=A  
如果\{an\}中的项全都是正整数，那么就称\[a1,a2,……,an,……\]为简单连分数，依\{an\}项数是否有限，分别称作有限（无限）简单连分数。  
如果\{an\}从某项开始存在周期，即存在t>0,对任意n>c,有a(n+t)=a(n),那么\[a1,a2,……,an,……\]记做\[a1,a2,……,a(c),\{a(c+1),……,a(c+t\}\],\{\}表示里面的项循环，周期为t。这种连分数称作循环连分数。  
这些名字和小数的叫法有点相似。  
  
定理7：每个正有理数都可写表示成有限简单连分数，且除了\[a,b,c……d\]和\[a,b,c……d-1,1\]这种差别外，表示的方法是唯一的。

定理8：每个正无理数都可以唯一的表示成无限简单连分数。

定理9：如果N>0不是一个平方数，那么√N可以唯一的表示成无限循环简单连分数。且  
√N=\[a,\{a1,a2,……，an,2a\}\]

奇偶连分数和pell方程的关系：

现在来看连分数和pell方程之间的联系。由x^2-dy^2=c,即(x+y√d)(x-y√d)=c,即  
x-y√d=c/(x+y√d),当x,y→∞时，x-y√d→0，x/y→√d，这就把pell方程和√d的渐进分数结合起来了，而连分数在某种程度上是对实数“最好”的近似。下面的定理明确揭示出这种关系：

定理10：如果√d=\[a,\{a1,a2,……，an,2a\}\],且\[a,a1,a2,……，an\]=x/y,(x,y)=1,那么x^2-dy^2=(-1)^(n+1).  
这个定理和定理3一起给出x^2-dy^2=1的基本解。  
事实上，对于√N的连分数，还有一个有趣的现象：循环部分是对称的。即  
√N=\[a,\{a1,a2,……，ak,ak,a(k-1),……,a2,a1,2a\}\]或者  
√N=\[a,\{a1,a2,……，ak,,a(k+1),ak,a(k-1),……,a2,a1,2a\}\]  
前者我们暂且把它称作偶连分式，后者称作奇连分式。

定理10可以重新表述为：x^2-dy^2=-1有解当且仅当√N的连分数是偶连分式。

定理11：若素数p=7(mod 8),则√d是奇连分数，√N=\[a,\{a1,a2,……，ak,,a(k+1),ak,a(k-1),……,a2,a1,2a\}\]，若\[a,a1,a2,……，ak\]=x/y,(x,y)=1,则x^2-py^2=2.反过来，若x^2-py^2=2有整数解，则p=2,或p=7(mod 8)  
  
定理12：若素数p=3(mod 8),则√d是奇连分数，√N=\[a,\{a1,a2,……，ak,,a(k+1),ak,a(k-1),……,a2,a1,2a\}\]，若\[a,a1,a2,……，ak\]=x/y,(x,y)=1,则x^2-py^2=-2.反过来，若x^2-py^2=2有整数解，则p=2,或p=3(mod 8)  
  
上面两条定理合起来可以表示为，若素数p=3(mod 4)，则x^2-py^2=2\*(-1)^((p+1)/4).

![20161113011557637][]

![20161113011602215][]

[20161220121950143]: /images/20220715/190d666db270431f9d3f6464e980a282.png
[20161113011557637]: /images/20220715/af966f1583e64400ac8737fb53ca3831.png
[20161113011602215]: /images/20220715/5b9025588d4d4ac7834a12bbd85d9d19.png