本帖最后由 hbghlyj 于 2024-10-3 08:58 编辑
Pell方程 By Ada 1 概述 古希腊数学家阿基米德曾提出一个所谓的“牲畜问题”，此问题最后归结为求解二元二次不定方程$x^{2}-472949 y^{2}=1$.现代欧洲关于Pell方程的历史源于1657年,费马重新提出求解不定方程$x^{2}-D y^{2}=1$的解的问题，其中$D$ 为非完全平方的正整数，他猜想此方程有无穷多组正整数解.沃利斯（J.Wallis,1616--1703）彻底解决了这个问题.佩尔（J.Pell,1611--1685）在他的一本著作中附录了沃利斯的结果，欧拉在他1732年发表的一篇论文中错误地称$x^{2}-D y^{2}=1$为Pell方程，这个错误就沿袭至今. 其实，通常的Pell方程[5]是指下面的不定方程 $x^{2}-D y^{2}= \pm 1, \pm 4$ $(x, y \in z)$， 其中$D$是非完全平方的正整数. 广义的Pell方程是上述不定方程的推广，有以下两种基本类型 $x^{2}-D y^{2}=k$ $(x, y, k \in z)$， $a x^{2}-b y^{2}= \pm 1, \pm 2, \pm 4$ $(x, y, a, b \in z, \quad a b \neq 0)$. 我们将上述四种不定方程统称为Pell方程. Pell方程是最古老的数论方程之一，这个方程在希腊人和印度人中间有着悠久的历史.公元4—5世纪时，印度人在求$\sqrt{2}$的近似值前就曾得到不定方程$x^{2}-2 y^{2}=1$有解$(x, y)=(3,2),(17,12),(577,408)$.同时，毕达哥拉斯学派也得到$x^{2}-2 y^{2}= \pm 1$的一个递推公式.阿基米德也得出$x^{2}-3 y^{2}=1$的一个解$(x, y)=(1351,780)$.关于Pell方程$x^{2}-D y^{2}=1$，印度人在七世纪时已经得出了相当丰富的成果：这个方程存在无穷组整数解，且任何一组解都可以由某一特殊解（基本解）表示出来，从而问题可以归结为求其基本解.1759年，欧拉通过把$\sqrt{D}$展成连分数而给出解$x^{2}-D y^{2}=1$的方法.（他的想法是：若$x, y$满足方程$x^{2}-D y^{2}=1$，则$\frac{x}{y}$是$\sqrt{D}$的很好的近似值），但是，他不能证明他的方法总能求出解，并且不能证明所有解都能够由$\sqrt{D}$的连分数展开给出来，直到1766年，拉格朗日才完全解决了这个问题.除了用连分数的方法外，人们还发现，可以令$y=1,2,3, \cdots$代入$D y^{2}+1$中，直到其为一完全平方数，然而无论是用连分数还是实验法，都往往要进行冗长的计算，而且只能针对具体的$D$来求解.对于求最小解是解决Pell方程的一个关键，因此杨仕椿$[3]$将其列为尚未解决的15个著名的不定方程的问题之一.而对于方程$x^{2}-D y^{2}=-1$的研究发现，它并不总有解，并且找到了一些判别其有无整数解的情况.例如Pell方程$x^{2}-1141 y^{2}=1$，当$1 \leq y \leq 1025$时均无解，它的基本解$x_{0}+y_{0} \sqrt{1141}$中的解$y_{0}=30693385322765657197397208$. 2 Pell方程$x^{2}-D y^{2}=1$ 我们将证明如下定理 定理1 设$D$是非完全平方的正整数，则方程 $x^{2}-D y^{2}=1$ (1) 有无穷多组整数解$x, y$.设$x_{0}^{2}-D y_{0}^{2}=1, x_{0}>0, y_{0}>0$是所有$x>0, y>0$的解中使$x+y \sqrt{D}$最小的那组解（称$\left(x_{0}, y_{0}\right)$为（1）的基本解），则（1）的全部解$x, y$，由 $x+y \sqrt{D}= \pm\left(x_{0}+y_{0} \sqrt{D}\right)^{n}$ （2）表出，其中$n$ 是任意整数. 为此，我们先引入几个引理 引理1$[4]$ 设$\theta$是一个无理数，且$q>1$是任给的一个整数，则存在整数$x, y$，使 $|x-y \theta|<\frac{1}{q}, 0<y \leq q$ （3） 推论1 有无穷多对整数$x, y$适合不等式 $|x-y \theta|<\frac{1}{y}$ （4） 引理2$[4]$ 设$D$不是平方数,$D>0$,则存在无穷多对整数$x, y$，使得 $\left|x^{2}-D y^{2}\right|<1+2 \sqrt{D}$ (5) 引理3$[4]$ 设$D$不是平方数， $D>0$,则存在整数$k$,$0<|k|<1+2 \sqrt{D}$,使得 $x^{2}-D y^{2}=k$ （6） 有无穷多组整数解$x, y$. 推论2 设$D$不是平方数， $D>0$,则存在整数$k$,$0<|k|<1+2 \sqrt{D}$,使得（6）有无穷多组整数解$x>0, y>0$. 定理1的证明： 首先证明$x^{2}-D y^{2}=1$至少有一组解$x \neq 0, y \neq 0$由推论2有(6)的解$x>0, y>0$有无穷多组 因而其中至少存在两组不同的解$\left(x_{1}, y_{1}\right) \neq\left(x_{2}, y_{2}\right), x_{i}>0, y_{i}>0, i=1,2$且满足 $x_{1} \equiv x_{2}(\bmod |k|), y_{1} \equiv y_{2}(\bmod |k|)$ （7） 于是 $\left(x_{1}^{2}-D y_{1}^{2}\right)\left(x_{2}^{2}-D y_{2}^{2}\right)=\left(x_{1} x_{2}-D y_{1} y_{2}\right)^{2}-D\left(x_{1} y_{2}-x_{2} y_{1}\right)^{2}=k^{2}$. $X=x_{1} x_{2}-D y_{1} y_{2} \equiv 0(\bmod |k|), X=x k$ $Y=x_{1} y_{2}-x_{2} y_{1} \equiv 0(\bmod |k|), Y=y k$故$x, y$是整数，$x, y$是(1)的一组解，且$y \neq 0$不失一般性，可设$x>0, y>0$设$x_{0}, y_{0}$是(1)的基本解，记$\varepsilon=x_{0}+y_{0} \sqrt{D}$则满足 $x+y \sqrt{D}=\varepsilon^{\pi}(n>0)$ (8) 的解$x, y$是(1)的解，故给出(1)的一组解$x>0, y>0$又因为$\varepsilon>1$所以不同的$n$给出的解也不同. 从而(8)给出了无穷多组(1)的解$x>0, y>0$反之，(1)的任一组解$x>0, y>0$可表为(8)的形状. 否则，$x+y \sqrt{D}>x_{0}+y_{0} \sqrt{D}$必存在某个整数$n$使得 $\varepsilon^{\pi}<x+y \sqrt{D}<\varepsilon^{\pi+1}$上式两端同时乘以$\bar{\varepsilon}^{\pi}$，得 $1<(x+y \sqrt{D}) \bar{\varepsilon}^{-\pi}<\varepsilon$又$(x+y \sqrt{D}) \bar{\varepsilon}^{\pi}=u+v \sqrt{D}$$u, v$是(1)的一组解 由于$u+v \sqrt{D}>1$故$0<u-v \sqrt{D}=\frac{1}{u+v \sqrt{D}}<1$两式相加得$2 u>1, u>0$又$2 v \sqrt{D}=u+v \sqrt{D}-(u-v \sqrt{D})>1-1=0$,故$v>0$而$u+v \sqrt{D}<E$，矛盾. 这就说明了(1)的全部解$x>0, y>0$可表为(8). 运用这个结果(1)的全部解$x<0, y<0$可表为 $|x|+|y| \sqrt{D}=E^{\pi}, n>0$ 即 $x+y \sqrt{D}=-\varepsilon^{\pi}, n>0$ (9) (1)的全部解$x<0, y>0$可表为 $|x|+y \sqrt{D}=\varepsilon^{\pi}, n>0$ 即 $x+y \sqrt{D}=-\varepsilon^{-\pi}, n>0$ (10) (1)的全部解$x>0, y<0$可表为 $x+|y| \sqrt{D}=\varepsilon^{\pi}, n>0$ 即 $x+y \sqrt{D}=\varepsilon^{-\pi}, n>0$ (11) 由(8)(9)(10)(11)以及(1)的平凡解$x= \pm 1, y=0$知，(1)的全部解可表为(2). 推论3 对于任意给定的整数$d>0$,(1)存在无穷多组解$x, y$满足$y \equiv 0(m o d d)$. 定理1告诉我们，只要求出Pell方程$x^{2}-D y^{2}=1$的基本解，那么它的全部解能全部表示出来. (1)的基本解也可定义为(1)的解$x>0, y>0$中使$K$最小的或使$y$最小的解. 定理2[1] 设$\xi, \pi$是正整数，满足$\xi^{2}-D \eta^{2}=1$，且$\xi>\frac{1}{2} \eta^{2}-1$，则$\xi+\eta \sqrt{D}$是$x^{2}-D y^{2}=1$的基本解. 如何求$x^{2}-D y^{2}=1$的基本解？ 试验法：令$y=1,2,3,4 \ldots$直到$1+D y^{2}$是一个完全平方数，即可求出基本解$[4]$. 连分数法：可以把$\sqrt{D}$展开为连分数来求基本解$[6]$. 3 Pell方程$x^{2}-D y^{2}=-1$ (12) Pell方程$x^{2}-D y^{2}=1$有无穷多组解，但Pell方程$x^{2}-D y^{2}=-1$不总是有解.例如，当$D \equiv 0(\bmod 4)$或$D \equiv 3(\bmod 4)$时，$x^{2}-D y^{2}=-1$无解. 一般地，我们有 定理3 设$D$是一个非完全平方数，$D>0$若方程$x^{2}-D y^{2}=-1$有解，且设$a^{2}-D b^{2}=-1, a>0, b>0$是所有$x>0, y>0$的解中使$x+y \sqrt{D}$最小的那组解（$a, b$叫做基本解），则(12)的全部解（有无穷多组）$x, y$由 $x+y \sqrt{D}= \pm(a+b \sqrt{D})^{2 \pi+1}$ (13) 表出，其中$n$为任意整数，且 $\varepsilon=x_{0}+y_{0} \sqrt{D}=(a+b \sqrt{D})^{2}$ (14) 其中$x_{0}, y_{0}$是$x^{2}-D y^{2}=1$的基本解. 定理4$[4]$ 设$p \equiv 1(\operatorname{mod4})$是素数，则 $x^{2}-p y^{2}=-1$ (15) 有整数解. 证明： 设$x_{0}, y_{0}$是$x^{2}-p y^{2}=1$的基本解，显然$x_{0}, y_{0}$一奇一偶. 若$x_{0} \equiv 0(\bmod 2), y_{0} \equiv 1(\bmod 2)$则由$x_{0}^{2}-p y_{0}^{2}=1$有$-1 \equiv 1(\bmod 4)$，矛盾. 故只能是$x_{0} \equiv 1(\bmod 2), y_{0} \equiv 0(\bmod 2)$. 再由$\frac{x_{0}+1}{2}, \frac{x_{0}-1}{2}$相差1,知$\left(\frac{x_{0}+1}{2}, \frac{x_{0}-1}{2}\right)$=1 又$\frac{x_{0}+1}{2} \cdot \frac{x_{0}-1}{2}=\frac{x_{0}^{2}-1}{4}=\frac{p y_{0}^{2}}{4}=p\left(\frac{y_{0}}{2}\right)^{2}$得 $\frac{x_{0}-1}{2}=p u^{2}$$\frac{x_{0}+1}{2}=v^{2}$从而 $y_{0}=2 u v, u>0, v>0$. (16) 或 $\frac{x_{0}-1}{2}=u^{2}$$\frac{x_{0}+1}{2}=p v^{2}$从而 $y_{0}=2 u v, u>0, v>0$. (17) (16)给出$v^{2}-p u^{2}=1$而$u=\frac{y_{0}}{2 v}<y_{0}$与$y_{0}$是基本解矛盾. (17)给出$u^{2}-p v^{2}=-1$故(15)有整数解$x=u, y=v$ 定理5$[7]$ 设$\phi$是一个素数，$2 p=r^{2}+s^{2}, r \equiv \pm 3(\bmod 8), s \equiv \pm 3(\bmod 8)$则$x^{2}-2 p y^{2}=-1$无整数解. 定理3的证明： 设$(a+b \sqrt{D})^{2}=u+v \sqrt{D}$,则$(a-b \sqrt{D})^{2}=u-v \sqrt{D}$. 故 $u^{2}-D v^{2}=\left(a^{2}-D b^{2}\right)^{2}=(-1)^{2}=1$即 $u, v$是$x^{2}-D y^{2}=1$的一组解. 现在证明 (14)给出了$x^{2}-D y^{2}=1$的基本解. 若不然，则另有基本解 $1<x_{1}+y_{1} \sqrt{D}<x_{0}+y_{0} \sqrt{D}=(a+b \sqrt{D})^{2}$ (18) 由$\frac{1}{a+b \sqrt{D}}=-a+b \sqrt{D}>0$及(18)有 $-a+b \sqrt{D}<\left(x_{1}+y_{1} \sqrt{D}\right)(-a+b \sqrt{D})<a+b \sqrt{D}$ (19) 令$\left(x_{1}+y_{1} \sqrt{D}\right)(-a+b \sqrt{D})=a_{1}+b_{1} \sqrt{D}$其中 $a_{1}=-x_{1} a+y_{1} b D, b_{1}=x_{1} b-y_{1} a$而$a_{1}^{2}-D b_{1}^{2}=-1$于是 (19)可写为 $0<-a+b \sqrt{D}<a_{1}+b_{1} \sqrt{D}<a+b \sqrt{D}, b_{1} \neq 0$. (20) 显然，$a_{1}+b_{1} \sqrt{D} \neq 1$ 若$a_{1}+b_{1} \sqrt{D}>1$，则 $1<a_{1}+b_{1} \sqrt{D}<a+b \sqrt{D}$ (21) 从而 $0<-a_{1}+b_{1} \sqrt{D}<1$ (22) 由(21)(22)可得$b_{1}>0,2 a_{1}=a_{1}+b_{1} \sqrt{D}-\left(-a_{1}+b_{1} \sqrt{D}\right)>1-1>0$即$a_{1}>0$此与$a+b \sqrt{D}$的定义矛盾. 若$a_{1}+b_{1} \sqrt{D}<1$，则由(20)有 $0<a_{1}+b_{1} \sqrt{D}<1$， $1<-a_{1}+b_{1} \sqrt{D}<a+b \sqrt{D}$得$b_{1}>0,-a_{1}>0$而$\left(-a_{1}\right)^{2}-D b_{1}^{2}=-1$，此与$a+b \sqrt{D}$的选择矛盾. 对于任意的$n$，式(13)给出的$x, y$显然是(12)的解. 反之，设$x, y$是(12)的任一组解，设 $(x+y \sqrt{D})(-a+b \sqrt{D})=x^{\prime}+y^{\prime} \sqrt{D}$ (23) 其中 $x^{\prime}=-a x+b y D, y^{\prime}=b x-a y$从而 $(x-y \sqrt{D})(-a-b \sqrt{D})=x^{\prime}-y^{\prime} \sqrt{D}$ (24) 两式相乘得 $x^{\prime}, y^{\prime}$是$x^{2}-D y^{2}=1$的一组解. 由定理1知，$x^{\prime}+y^{\prime} \sqrt{D}= \pm\left(x_{0}+y_{0} \sqrt{D}\right)^{n}$，$n$为整数 由(23)和(14)得 $x+y \sqrt{D}= \pm(a+b \sqrt{D})^{2 \pi+1}$，$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..The quadratic form $x^{2}-2 p y^{2}$.J.Number theory,1978(10) :10-15. | 
realnumber
发表于 2019-3-15 21:02
hbghlyj
发表于 2023-4-18 06:34
