Pell方程

Pell方程ByAda1概述古希腊数学家阿基米德曾提出一个所谓的“牲畜问题”，此问题最后归结为求解二元二次不定方程224729491xy.现代欧洲关于Pell方程的历史源于1657年,费马重新提出求解不定方程221xDy的解的问题，其中D为非完全平方的正整数，他猜想此方程有无穷多组正整数解.沃利斯（J.Wallis,1616--1703）彻底解决了这个问题.佩尔（J.Pell,1611--1685）在他的一本著作中附录了沃利斯的结果，欧拉在他1732年发表的一篇论文中错误地称221xDy为Pell方程，这个错误就沿袭至今.其实，通常的Pell方程]5[是指下面的不定方程221,4xDy(,)xyz，其中D是非完全平方的正整数.广义的Pell方程是上述不定方程的推广，有以下两种基本类型22xDyk(,,)xykz，221,2,4axby(,,,0)xyabzab，.我们将上述四种不定方程统称为Pell方程.Pell方程是最古老的数论方程之一，这个方程在希腊人和印度人中间有着悠久的历史.公元4—5世纪时，印度人在求2的近似值前就曾得到不定方程2221xy有解(,)(3,2),(17,12),(577,408)xy.同时，毕达哥拉斯学派也得到2221xy的一个递推公式.阿基米德也得出2231xy的一个解(,)(1351,780)xy.关于Pell方程221xDy，印度人在七世纪时已经得出了相当丰富的成果：这个方程存在无穷组整数解，且任何一组解都可以由某一特殊解（基本解）表示出来，从而问题可以归结为求其基本解.1759年，欧拉通过把D展成连分数而给出解221xDy的方法.（他的想法是：若,xy满足方程221xDy，则xy是D的很好的近似值），但是，他不能证明他的方法总能求出解，并且不能证明所有解都能够由D的连分数展开给出来，直到1766年，拉格朗日才完全解决了这个问题.除了用连分数的方法外，人们还发现，可以令1,2,3,y代入21Dy中，直到其为一完全平方数，然而无论是用连分数还是实验法，都往往要进行冗长的计算，而且只能针对具体的D来求解.对于求最小解是解决Pell方程的一个关键，因此杨仕椿]3[将其列为尚未解决的15个著名的不定方程的问题之一.而对于方程221xDy的研究发现，它并不总有解，并且找到了一些判别其有无整数解的情况.例如Pell方程2211411xy，当11025y时均无解，它的基本解001141xy中的解030693385322765657197397208y.2Pell方程221xDy我们将证明如下定理定理1设D是非完全平方的正整数，则方程221xDy(1)有无穷多组整数解,xy.设2200001,0,0xDyxy是所有0,0xy的解中使xyD最小的那组解（称00(,)xy为（1）的基本解），则（1）的全部解,xy，由00()nxyDxyD（2）表出，其中n是任意整数.为此，我们先引入几个引理引理1]4[设是一个无理数，且1q是任给的一个整数，则存在整数,xy，使1,0xyyqq（3）推论1有无穷多对整数,xy适合不等式1xyy（4）引理2]4[设D不是平方数,0D,则存在无穷多对整数,xy，使得2212xDyD(5)引理3]4[设D不是平方数，0D,则存在整数k,012kD,使得22xDyk（6）有无穷多组整数解,xy.推论2设D不是平方数，0D,则存在整数k,012kD,使得（6）有无穷多组整数解0,0xy.定理1的证明：首先证明122Dyx至少有一组解.0,0yx由推论2有(6)的解0,0yx有无穷多组因而其中至少存在两组不同的解.2,1,0,0,,,2211iyxyxyxii且满足.mod,mod2121kyykxx（7）于是.2212212212122222121kyxyxDyDyxxDyxDyx,,mod02121xkXkyDyxxX,,mod01221ykYkyxyxY故yx,是整数，yx,是(1)的一组解，且.0y不失一般性，可设.0,0yx设00,yx是(1)的基本解，记,00Dyx则满足)0(nDyxn(8)的解yx,是(1)的解，故给出(1)的一组解.0,0yx又因为,1所以不同的n给出的解也不同.从而(8)给出了无穷多组(1)的解.0,0yx反之，(1)的任一组解0,0yx可表为(8)的形状.否则，,00DyxDyx必存在某个整数n使得1nnDyx上式两端同时乘以n，得nDyx1又,DvuDyxnvu,是(1)的一组解由于,1Dvu故110DvuDvu两式相加得.0,12uu又0112DvuDvuDv,故.0v而Dvu，矛盾.这就说明了(1)的全部解0,0yx可表为(8).运用这个结果(1)的全部解0,0yx可表为0,nDyxn即0,nDyxn(9)(1)的全部解0,0yx可表为0,nDyxn即0,nDyxn(10)(1)的全部解0,0yx可表为0,nDyxn即0,nDyxn(11)由(8)(9)(10)(11)以及(1)的平凡解0,1yx知，(1)的全部解可表为(2).推论3对于任意给定的整数,0d(1)存在无穷多组解yx,满足dymod0.定理1告诉我们，只要求出Pell方程122Dyx的基本解，那么它的全部解能全部表示出来.(1)的基本解也可定义为(1)的解0,0yx中使x最小的或使y最小的解.定理2]1[设,是正整数，满足122D，且1212，则D是122Dyx的基本解.如何求122Dyx的基本解？试验法：令4,3,2,1y直到21Dy是一个完全平方数，即可求出基本解]4[.连分数法：可以把D展开为连分数来求基本解]6[.3Pell方程122Dyx(12)Pell方程122Dyx有无穷多组解，但Pell方程122Dyx不总是有解.例如，当4mod0D或4mod3D时，122Dyx无解.一般地，我们有定理3设D是一个非完全平方数，,0D若方程122Dyx有解，且设0,0,122baDba是所有0,0yx的解中使Dyx最小的那组解（ba,叫做基本解），则(12)的全部解（有无穷多组）yx,由12nDbaDyx(13)表出，其中n为任意整数，且200DbaDyx(14)其中00,yx是122Dyx的基本解.定理4]4[设4mod1p是素数，则122pyx(15)有整数解.证明：设00,yx是122pyx的基本解，显然00,yx一奇一偶.若2mod1,2mod000yx则由12020pyx有4mod11，矛盾.故只能是2mod0,2mod100yx.再由21,2100xx相差1,知)21,21(00xx=1又2020200024412121yppyxxx得,2120pux2021vx从而.0,0,20vuuvy(16)或,2120ux2021pvx从而.0,0,20vuuvy(17)(16)给出,122puv而,200yvyu与0y是基本解矛盾.(17)给出,122pvu故(15)有整数解.,vyux推论4(16)的全部解yx,由12npvupyx表出，其中n为任意整数，vu,由(17)给出.下面给出一个4mod11222ppyx无整数解的例子.例Pell方程13422yx无整数解.,yx定理5]7[设p是一个素数，,8mod3,8mod3,222srsrp则1222pyx无整数解.定理3的证明：设DvuDba2,则DvuDba2.故11222222DbaDvu即vu,是122Dyx的一组解.现在证明(14)给出了122Dyx的基本解.若不然，则另有基本解200111DbaDyxDyx(18)由01DbaDba及(18)有DbaDbaDyxDba11(19)令DbaDbaDyx1111其中aybxbbDyaxa111111,而12121Dba于是(19)可写为.0,0111bDbaDbaDba(20)显然，111Dba若111Dba，则DbaDba111(21)从而1011Dba(22)由(21)(22)可得0112,0111111DbaDbaab即.01a此与Dba的定义矛盾.若111Dba，则由(20)有1011Dba，DbaDba111得.0,011ab而12121Dba，此与Dba的选择矛盾.对于任意的n，式(13)给出的yx,显然是(12)的解.反之，设yx,是(12)的任一组解，设DyxDbaDyx(23)其中aybxybyDaxx,从而DyxDbaDyx(24)两式相乘得yx,是122Dyx的一组解.由定理1知，nDyxDyx00，n为整数由(23)和(14)得12nDbaDyx，n为整数.参考文献[1]潘成洞，潘成彪.初等数论[M].北京：北京大学出版社，1992.[2]闵嗣鹤，严士健.初等数论[M].北京：高等教育出版社，1982.[3]杨仕椿，15个著名的不定方程问题[J].数学通讯，1996,9:25-28.[4]柯召，孙琦.谈谈不定方程[M].哈尔滨：哈尔滨工业大学出版社，2011.[5]张德馨.整数论[M].哈尔滨：哈尔滨工业大学出版社，2011.[6]华罗庚.华罗庚文集[M].北京：科学出版社，2010.[7]Lienen,V.H..Thequadraticform222pyx.J.Numbertheory,1978(10):10-15.