初等数论入门 Lesson 10 连分数与佩尔方程

连分数

对于任意一个实数 $\alpha$，我们不断进行如下操作：

$$\alpha_n=a_n+\dfrac 1 {\alpha_{n+1}}$$

最终得到的序列：$[a_0;a_1;a_2;a_3,\cdots]$ 记为简单连分数

且有理数一定数有限连分数，无理数一定是无限连分数

渐近分数

Convergents

我们对于无限连分数，截断到第 $k$ 项，记为第 $k$ 个渐近分数。

它们遵循二阶线性递推关系：

$$\begin{cases} p_k = a_k p_{k-1} + p_{k-2} \\ q_k = a_k q_{k-1} + q_{k-2} \end{cases}$$

由此我们可以证明一个关键恒等式：

$$p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}$$

因此这意味这 $\gcd{p_k,q_k}=1$，即我们用这种方式构造的渐近分数均为最简分数

最佳逼近定理

对于第 $k$ 个渐近分数 $\frac{p_k}{q_k}$，任意一个分数 $\frac{m}{n}$（其中 $0 < n \le q_k$），只要 $\frac{m}{n} \neq \frac{p_k}{q_k}$，那么它到 $\alpha$ 的距离一定大于 $\frac{p_k}{q_k}$ 到 $\alpha$ 的距离。 即：

$$\left|\alpha - \frac{m}{n}\right| > \left|\alpha - \frac{p_k}{q_k}\right|$$

这有利于我们估计去估算 $\sqrt D$

还有一点，这个逼近是上下交替逼近

二次无理数周期性

• 二次无理数：$a+b\sqrt D$
• 拉格朗日定理：任何一个二次无理数必然是循环的：$\left[a_0;\,\overline{a_1,a_2,\dots,a_l}\right]$
• 伽罗瓦纯循环判定：一个一个二次无理连分数为纯循环，当且仅当它的简约二次无理数 $\alpha >1$，且其代数共轭（根号部分取负，整数部分不变）$\alpha'\in(0,1)$

如果是单纯的 $\sqrt D$，则更有：

$$\sqrt{D} = \left[a_0;\overline{a_1,a_2,\dots,a_{l-1},2a_0}\right]$$

循环节的最后一项必然为 $2a_0$

连分数求解佩尔方程

核心判定定理：

• 对于 $x^2 - Dy^2 = 1$，其正整数解 $(x,y)$ 一定出现在 $\sqrt{D}$ 的渐近分数 $\dfrac{p_k}{q_k}$ 中。

具体的：

若循环节长度为 $l$，渐近分数 $\dfrac{p_{l-1}}{q_{l-1}}$ 满足：

$$p_{l-1}^2 - D q_{l-1}^2 = (-1)^l$$