佩尔方程的最小解

fungarwai

为什么可以用渐进连分数找出佩尔方程的最小解？

佩尔方程：http://zh.wikipedia.org/wiki/%E4%BD%A9%E5%B0%94%E6%96%B9%E7%A8%8B

liangbch

$ x^2 -ny^2=1 $
$ \implies  x^2 = n.y^2 + 1 $
$ \implies  x^2 = (\sqrt{n}.y)^2 + 1 $
略去常数项 1, $\implies x^2 \approx  (sqrt(n).y)^2 $
$\implies x \approx    \sqrt{n}.y $
$\implies  x/y \approx  \sqrt{n}$
故$x/y$ 为n的渐进连分数

fungarwai

liangbch 发表于 2014-6-17 17:27
$ x^2 -ny^2=1 $
$ \implies  x^2 = n.y^2 + 1 $
$ \implies  x^2 = (\sqrt{n}.y)^2 + 1 $

非标准型那个可以吗？

liangbch

1. $\sqrt{2}$的渐进连分数的前几个是1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408。你说的141/100不能称为$\sqrt{2}$的渐进连分数。

数学上可以证明，由（狭义）连分数得到的渐近分数，在分子或分母小于下一个渐进分数的分数中，其值是最接近精确值的近似值。


2. 在所有渐近分数序列中，第奇数个渐近分数总是小于目标无理数，第偶数个渐近分数总是大于目标无理数。佩尔方程的有2种形式，第一种是 $x^2-ny^2=1$,第2种是 $x^2-ny^2=-1$,对于前一种，x/y应取比$\sqrt{n}$大的渐进分数.

fungarwai

测试最小解的话，$x^2-7y^2=1$中y从1开始试

$(x^2,y^2)=(8,1),(29,4),(64,9)$即得$(x,y)=(8,3)$，为何还要用渐进连分数？

fungarwai

好吧，虽然我觉得还是试探法比较容易。

遇到非标准型$ax^2-by^2=c$要怎么用渐进连分数？还是$\sqrt{\frac{b}{a}}$？

liangbch

kastin 说的 “(不太严格）”是对的。关于Pell方程的解法，请参阅潘承洞的《初等数论》 第七章，第六节(372页)，见本站百度网盘分享http://pan.baidu.com/s/1o618EFo，下面的文字摘自上文


这一节我们应用连分数理论来解不定方程

$  x^2-dy^2=1,                 (1) $
$  x^2-dy^2=-1,                (2) $

这里d是非平方数，$d>1$. 通常这类方程称为Pell方程，满足$x>0,y>0$的解称为正解。
  
  定理1  设$\zeta_0=\sqrt{d}$,它的循环连分数周期为$l$,渐进分数为$h_n/k_n$,那么，
  
  $(i)$ 当$l$为偶数时，不定方程$(2)$无解，不定方程$(1)$的全体正解为
  
    $ x=h_{jl-1},  y=k_{jl-1},  j=1,2,3 \ldots           (3) $

  $(ii)$ 当$l$为奇数时，不定方程$(2)$的全体正解为

    $ x=h_{lj-1},  y=k_{lj-1},  j=1,3,5 \ldots           (4) $
                     
  不定方程(1)的全体正解为
    $ x=h_{lj-1},  y=k_{lj-1},  j=2,4,6 \ldots           (5) $

kastin

fungarwai 发表于 2014-6-17 23:13
好吧，虽然我觉得还是试探法比较容易。

遇到非标准型$ax^2-by^2=c$要怎么用渐进连分数？还是$\sqrt{\fra ...

下面是曾经看一般连分数理论书籍的一些笔记，简化后部分摘录于下：
规定`a_0,a_1,...,a_n,..`均为非负整数，形如$$\frac{p_n}{q_n}=a_0+\frac{1}{a_1+\dfrac{1}{a_2+...+\dfrac{1}{a_n}}}$$称之为简单连分数（因为分子都是1,在一般连分数理论中，分子可以不是1的），记作`[a_0;a_1,a_2,...,a_n]`，其中`a_0,a_1,...,a_n,..`称为部分商。

根据简单连分数的定义式可得
$$\tag{1}\begin{cases}p_{n+1}=a_{n+1}p_{n}+p_{n-1} \\
q_{n+1}=a_{n+1}q_n+q_{n-1} \end{cases}$$若将连分数中第`k+1`个部分商`a_k`之后的项截去，则称剩下的截断连分数`\dfrac{p_k}{q_k}`为原来连分数的`k`阶渐近(分数)。

根据上述定义方程，将n适当延拓到-1,-2，根据数学归纳法有渐进分数的之间的关系
递归性质1：$$\tag{2-1}p_nq_{n-1}-p_{n-1}q_n=(-1)^{n+1}$$两端同时除以`q_nq_{n-1}`后，得$$\tag{2-2}[a_0;a_1,a_2,...,a_n]-[a_0;a_1,a_2,...,a_{n-1}]=\frac{(-1)^{n+1}}{q_nq_{n-1}}$$这就是说，相邻渐进分数之间相差一个单位分数（分子是1的分数），即连分数是上下交替收敛于实数值的。
另外，从(2-2)中我们还得到连分数分数的一条单调性质：
对于任意整数`s,t \geqslant 0`，$$\dfrac{p_{2s+1}}{q_{2s+1}}>\dfrac{p_{2t}}{q_{2t}}$$那么阶数相间为1的渐进分数之间的关系如何呢？将(1)中消去`p_{n-1}`和`q_{n-1}`，并利用(2-1)得
递归性质2：$$\tag{3-1}p_nq_{n-2}-p_{n-2}q_n=(-1)^na_n$$两端同时除以`q_nq_{n-2}`后，得$$\tag{3-2}[a_0;a_1,a_2,...,a_n]-[a_0;a_1,a_2,...,a_{n-2}]=\frac{(-1)^na_n}{q_nq_{n-2}}$$因为`a_n \geqslant 0`，所以我们又得到一条关于连分数分数的单调性质：$$\frac{p_1}{q_1}>\frac{p_3}{q_3}>\frac{p_5}{q_5}>\cdots \quad(奇数阶单调递减)\\\frac{p_0}{q_0}<\frac{p_2}{q_2}<\frac{p_4}{q_4}<\cdots\quad( 偶数阶单调递增)$$也就是说，奇数阶渐近分数值是递减的，直到收敛于被展开的那个实数；偶数阶渐进分数值是递增的，直到收敛于被展开的那个实数。

下面还有几条关于无理数展开为连分数的性质，有的证明很简单，有的较为复杂，下面直接列出
1) 任何无理数可 唯一地 表成无限简单连分数。
2)（Lagrange定理）一个无理数可用循环简单连分数表示当且仅当它是二次代数数（即不可约整系数二次方程`ax^2+bx+c=0`的根）。这时候，连分数一定是从某一项开始循环。
3) 特别地，对于二次无理数(即非平方数的二次方根)`\sqrt{d}`，其连分数形式是从第二项`a_1`开始循环，且循环是对称的，循环节长度为`m`，且循环节末尾是`2a_0`。即$$\sqrt{d}=[a_0,a_1,...,a_{m-1},2a_0,
a_1,...,a_{m-1},2a_0,a_1,...,a_{m-1},2a_0,...]$$且有对称性`a_1=a_{m-1}, a_2=a_{m-2},...`.
4) 无理数`\alpha`可写成无穷连分数形式，利用(1)和(2-1)，有不等式关系$$\frac{1}{q_n(q_n+q_{n+1})}<\left|\alpha-\frac{p_n}{q_n}\right| < \frac{1}{q_nq_{n+1}}$$
其实，根据(3-2)我们还可以得到推论：
所有实数都可以写成交错级数的形式，特别地，无理数可以写成无穷交错级数。$$\sum_{n=1}^{\oo}a_0+\frac{(-1)^{n+1}}{q_nq_{n-1}}$$以上是连分数常用的基本性质，下面我们来解决佩尔方程的问题。

首先，考虑佩尔方程的标准形式$$\tag{4}x^2-Dy^2=1$$显然方程有一组平凡解：(1,0)，我们要找的是非平凡解。非平凡解`(x_i,y_i)`中，最小的那一组解被称为方程的基本解（最小解）。
若`D`是有理数，只有当`D`是非完全平方数时才有无穷多组解（因为若D是某个有理数的平方，则方程总可以化为两个二元线性方程组的正整数解，这时非平凡解一定是有限多个或者没有）。

先来证明方程(4)的基本解`(x_0,y_0)`是`\sqrt{D}`的渐进分数的分子和分母。
证明：因为$$(x_0-\sqrt{D}y_0)=\frac{1}{(x_0+\sqrt{D}y_0)}$$l两端同时除以`y_0`$$\frac{x_0}{y_0}-\sqrt{D}=\frac{1}{y_0^2(\frac{x_0}{y_0}+\sqrt{D})}$$
而`x_0-\sqrt{D}y_0>0`，所`\sqrt{D}<\frac{x_0}{y_0}`，于是$$0<\left| \sqrt{D}-\frac{x_0}{y_0} \right|<\frac{1}{2y_0^2\sqrt{D}}<\frac{1}{y_0^2\lfloor\sqrt{D}\rfloor}$$
因为二次无理数连分式展开的第一个部分商`a_0=\lfloor \sqrt{D} \rfloor`，所以，根据上面提到的无理数连分数展开的性质1和4，我们可知`\frac{x_0}{y_0}`是`\sqrt{D}`的某阶渐近分数。
如何求方程(4)的解呢？
考虑将`\sqrt{D}`化为无穷连分数形式`\dfrac{p_n}{q_n}\,(n\to \oo)`，设循环节长度为`m`。那么连分数$$[a_0,a_1,...,a_{m-1},2a_0,a_1,...,a_{m-1},2a_0,...,a_1,...,a_{m-1}]$$便是`\sqrt{D}`的`mk-1`阶渐近分数，这里`k`指的是`a_1,...,a_{m-1}`那一段重复的次数。
若`x_k`和1`y_k`分别是`\sqrt{D}`的`mk-1`阶渐近分数的分子和分母，可证明$$x_k^2-Dy_k^2=(-1)^{mk}$$ 因为k从最小取起，`x_k`,`y_k`也相应从小到大，于是(4)的基本解（最小解）便存在于其中。
因此，令$$k=\begin{cases}1,2,3,... &(m为偶数) \\
2,4,6,... &(m为奇数)\end{cases}$$
我们便可得到Pell方程`x^2-Dy^2=1`的无穷多组正整数解。

考察如下形式的佩尔方程$$\tag{5}ax^2-by^2=c$$这里`\gcd(a,b,c)=1`，否则`a,b,c`同时除以`\gcd(a,b,c)`作为新的`a,b,c`.
很明显上述方法在这里并不总有效。举个例子
`x^2-2y^2=7`的最小解是(3,1)，但是`\sqrt{2}`的渐进分数中1,3/2,7/5,17/12,...没有3/1这个分式.
要知道，并不是对于任意的`c`方程都有解。

根据上面的分析过程，我们可以知道，对于满足`(-1)^{n+1}c=p_n^2-Dq_n^2`的`c`可以通过`\sqrt{D}`的渐近分数来求方程(5)的基本解，而其他的`c`可能有解可能无解，但无法用`\sqrt{D}`渐近分数来求(5)的基本解。