有限簡單連分數的逼近原理在Pell 方程上的應用

鄧從政

（凱里學院，貴州凱里 556011）

0 引言

形如x2-dy2=±1 的不定方程即Pell 方程，當其參數d為開方開不盡的正整數時，用一般的初等方法難以求解，解析其解的構造更加困難.其解的形態與有限簡單連分數貌似相距甚遠，卻有著緊密的聯系.本文從有限簡單連分數的性質及其與有理分數的關系出發，巧用有限簡單連分數的獨特性質，用逼近原理來探討兩類Pell方程的解法及其解的關系，從理論上闡述用逼近原理解Pell方程的有效性，并為研究這類不定方程解的構造提供一個簡潔而實用的方法.

1 關于有限簡單連分數的幾個定理

定義設a0,a1,a2,???是一個無限整數列，aj≥1,j≥1.記有限簡單連分數

定義整數列{hn}與{kn}：

則，h0=a0，h1=a1a0+1，1=k0≤a1=k1＜k2＜???＜kn＜???，kn→+∞.

這里的{aj}，{hn}，{kn}就相當于有限簡單連分數定義中取整數的特殊情形［1］.

定理1有限簡單連分數，n≥0的值是有理分數，

其中hn，kn由定義1給出.特別地，還有

這就得到了ξ0=u0/u1的有限簡單連分數表示式.由于bs≥2，得

定理2設是個有限簡單連分數，an＞1,bs＞1.若

證明：不妨設s≥n.對n用歸納法.當n=0時，若s≥1，則得

由于bs＞1，所以，因此上式不可能成立.這就推出s=0，a0=b0.

所以結論當n=0時成立.假設當n=k(≥0)時結論成立.

當n=k+1時，注意到s≥n≥1，則

由歸納假設知，從上式就推得s=k+1及aj=bj，1≤j≤k+1.這就證明了當n=k+1時結論也成立.所以結論對一切n≥0都成立［1-3］.

定理3（逼近原理）設d＞1 不是平方數.若不定方程x2-dy2=±1 有解x=x0＞0，y=y0＞0.那么，一定是的某個漸近分數，且x0=h，y0=kn.

證明：由題意必有x0≥y0.否則從y0＞x0可推出±1=x02-dy02＜y02-dy02≤-y02≤-1.這是不可能的，由x0，y0是解及x0≥y0可得

逼近原理并未指出Pell 不定方程是否有解，但結論表明，我們只要在的漸近分數中去尋找到一個解，我們就可以探索出這類方程的某種解法，并求出方程的一般解.由此我們需要去研究的無限簡單連分數表示式的性質，從而找出Pell 方程的解法，并更進一步了解其解的關系和構造［4］.

2 兩類Pell方程的解法及其解的構造

下面我們用連分數的逼近原理來探討兩類Pell方程的解法及其解的構造

這里d是非平方數，d＞1，滿足x＞0,y＞0 解稱為正解.知道了方程的正解，很顯然±x,±y均是方程的解，因此我們只需求出Pell方程的正解［1］.

定理4設ξ0=，它的循環連分數周期為l，漸進分數為hn/kn.那么，

當l為偶數時，不定方程（2）無解，不定方程（1）的全體正解為

當l為奇數時，不定方程（2）的全部正解為

不定方程（1）的全部正解為

證明：若x,y是不定方程（1）或（2）的一組正解，那么必有某個n≥0使x=hn，y=kn.

當qj≠-1及當且僅當l｜j時qj=1知僅當n+1=jl(j＞0)時，hn=hlj-1，kn=klj-1才有可能是不定方程（1）或（2）的解，這時,j＞0.由此就推出方程的全部解.由于當x,y是不定方程（1）或（2）的解時，±x,±y（正、負號任意選取）也是不定方程（1）或（2）的解，再注意到±1,0是（1）的解，及h-1=1，k-1=0，從定理4立即得到如下推論.

推論1在定理4的符號和條件下，

當l為偶數時，不定方程（2）無解，不定方程（1）的全部解為

其中正、負號任意選取.

當l為奇數時，不定方程（2）的全部解為

不定方程（1）的全部解為

以上正、負號均為任意選取.

定理4 表明，為了求出不定方程（1）和（2）的全部正解，就要去求出的所有漸進分數hlj-1/klj-1(j=1,2,???).當然逐個去求不僅麻煩也是不可能的.下面將證明只要求出hl-1，kl-1，利用解與解之間的關系，其他的解都可用它表示出來，這種解的構造可以求出Pell 方程的通解，一般的，當x，y是不定方程（1）或（2）的正解時，我們就說二次無理數x+是不定方程（1）或（2）的正解［4］.

定理5設ξ0=，它的循環連分數的周期為l，漸近分數為hn/kn(n≥0)，那么有

證明：記pj=hlj-1+，它的共軛數.

定理4證明了不定方程（1）和（2）（有解的話）的全部正解由pj（j≥1）給出，易證

因此，對任意j＞1，必有正整數k滿足.

為了證明式（10），只要證明必有k=j.顯見，所有一定不是方程（1）或（2）的正解.由此及定理1 和式（13）就證明了和pj(j≥1)一樣，都分別給出了不定方程（1）和（2）的全部正解，因此，這兩個集合是一樣的.注意到（利用式（12）及p1＞1）

所以式（13）成立［5］.

推論2在定理4的符號和條件下，

當l為偶數時，不定方程（2）無解，不定方程（1）的全部解為

其中正、負號任意選取.

當l為奇數時，不定方程（2）的全部解為

不定方程（1）的全部解為

以上正負號均為任意選取【4】.顯見{hl-1,kl-1}是正解中的最小的.如果（2）有解，我們把{hl-1,kl-1}及p1=hl-1+稱為不定方程（2）的最小正解，{h2l-1,k2l-1}及p2=h2l-1+稱為（1）的最小正解；如果（2）無解，稱{hl-1,kl-1}，及p1為（1）的最小正解［1，6］.

例1 求不定方程

其周期為12，根據推論2可知，不定方程（20）無解.

不定方程（19）的最小正解是x=h11,y=k11，

由此得（19）全部解為x+,j=0,1,2,3,4,???.

例2 求不定方程

其周期為11，不定方程（21）的最小正解是x=h10,y=k10，

根據推論2可知，不定方程（21）的解為：

不定方程（22）的解為：

3 結束語

本文從有限簡單連分數的性質及其與有理分數的關系出發，巧用有限簡單連分數的獨特性質，用逼近原理來探討兩類Pell 方程的解法及其解的關系，從理論上闡述了用逼近原理解Pell 方程的有效性，這種解法還可以為破解RSA公鑰密碼提供很大的幫助［7］.