[數論] 連分數(Continued Fraction)

參考資料
1. 唐其鈺譯，方程的整數解，九章出版社，2002年出版，ISBN13：9799576032195
2. 認識連分數，林聰源，http://episte.math.ntu.edu.tw/articles/mm/mm_02_3_08/index.html
3. C.D.Olds(1963), Continued Fractions (New Mathmatical Library, Number 9)
    www.plouffe.fr/simon/math/Continued%20Fractions.pdf
4. Strayer(1994), Elementary Number Theory, Waveland Press, 1994/2002, ISBN 1-57766-224-5
5. Infinite continued fractions http://www.math.binghamton.edu/dikran/478/Ch7.pdf

0.一次不定方程
二元一次方程可表示為 $ax+by+c=0$，其中係數 $a$ 和 $b$ 是非零整數，$c$ 是任意整數。我們的目的是求出 $x$ 和 $y$ 的整數解。

一般我們會直接設 gcd$(a,b)=1$，也就是兩係數互質。它的一切整數解的公式是 $x=x_0-bt$，$y=y_0+at$，其中 $(x_0,y_0)$ 是一組解，$t$ 是整數。也就是說，只要我們能找到一組解，就可以用這組解去找到其他所有的解。

如何找出一組解？我們以下面的例子說明。

設有一方程式 $127x-52y+1=0$。先檢查 gcd$(127,52)=1$，而 $1$ 能整除 $1$，所以此方程式有整數解。我們的方法將假分數 $\frac{127}{52}$ 化成連分數形式。

1.1 有限簡單連分數(finite simple continued fraction)
分數 $a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+...+\frac{1}{a_{n}}}}$ 稱為「有限簡單連分數(finite  simple continued fraction)」，可用符號 $\left [ a_{1}, a_{2},...,a_{n} \right ]$ 表示有限連分數。

例如 $\left [ 0,3,2,4,3 \right ]=\frac{1}{3+\frac{1}{2+\frac{1}{4+\frac{1}{3}}}}$，$\left [ -2,3,2,1,5 \right ]=-2+\frac{1}{3+\frac{1}{2+\frac{1}{1+\frac{1}{5}}}}$。

例：試將 $\frac{37}{11}$ 表示為有限簡單連分數(Hint：輾轉相除法)

解：$\left\{\begin{matrix}37=11\times 3+4\\ 11=4\times 2+3\\ 4=3\times 1+1\\ 3=1\times 3+0\end{matrix}\right.$, 故 $\frac{37}{11}=[3,2,1,3]=3+\frac{1}{2+\frac{1}{1+\frac{1}{3}}}$.

任何一個有理數都能表示成有限簡單連分數，反之亦然，這是因為輾轉相除法必會在有限步驟結束。

回到一開始提到的方程 $127x-52y+1=0$，運用輾轉相除法原理，我們得到 $\frac{127}{52}=2+\frac{1}{2+\frac{1}{3+\frac{1}{1+\frac{1}{5}}}}=[2,2,3,1,5]$。去掉此連分數最後一個分數 $\frac{1}{5}$，並用原來的分數 $\frac{127}{52}$ 減去它：

$\frac{127}{52}-[2,2,3,1]=\frac{127}{52}-\left ( 2+\frac{1}{2+\frac{1}{3+\frac{1}{1}}} \right )=\frac{127}{52}-\frac{22}{9}=-\frac{1}{52\cdot 9}$.

將 $\frac{127}{52}-\frac{22}{9}=-\frac{1}{52\cdot 9}$ 通分，得到 $127\times 9-52\times 22+1=0$。對照 $127x-52y+1=0$，我們得到了一組解 $(x_0,y_0)=(9,22)$，也就是倒數第二個漸近分數的分母分子，因此全部的解就是 $\left\{\begin{matrix}x=9+52t\\ y=22+127t\end{matrix}\right.$，其中 $t$ 是整數。


1.2 為什麼可以透過這個方法求解？
關鍵在於「輾轉相除法」和連分數的性質。我們將 $\frac{127}{52}$ 化成連分數的過程表示如下。

$\left\{\begin{matrix}(a=b\times q+r)\\127=52\times 2+23\\ 52=23\times 2+6\\ 23=6\times 3+5\\ 6=5\times 1+1\\ 5=1\times 5+0\end{matrix}\right.$.

對照 $a=b\times q+r$，$r<b$ 的格式，其中 $q$ 是商數，$r$ 是餘數。連分數 $[2,2,3,1,5]$ 其實就是依序將商數排列而得。

對於一般連分數形式 $\frac{a}{b}=q_{1}+\frac{1}{q_2+\frac{1}{q_3+_{\; \; \ddots \frac{1}{q_{n-1}+\frac{1}{q_n}}}}}=[q_1,q_2,\cdots ,q_n]$，若我們只取到連分數的某一環節，例如第 $k$ 個環節 $\delta _k=\frac{P_k}{Q_k}$，其餘部分捨棄，這個分數稱為「漸近分數(convergent)」或「近似分數」。根據這個定義，當 $k=n$ 時，$\delta _n=\frac{P_n}{Q_n}$ 其實就是 $\frac{a}{b}$ 本身。

我們將在下面證明，當 $k=n$ 時，有 $\delta _n-\delta _{n-1}=\frac{(-1)^n}{Q_nQ_{n-1}}$，即 $\frac{a}{b}-\frac{P_{k-1}}{Q_{k-1}}=\frac{(-1)^n}{Q_nQ_{n-1}}$。在等號兩邊同乘上 $Q_nQ_{n-1}$，又 $Q_n=b$，於是得到 $aQ_{n-1}-bP_{n-1}+(-1)^{n-1}=0$。最後用 $(-1)^{n-1}c$ 乘之，得到

$a\left [ (-1)^{n-1}c\cdot Q_{n-1} \right ]+b\left [ (-1)^{n-1}c\cdot P_{n-1} \right ]+c=0$.

這就是求 $ax+by+c=0$ 方程的一組解的公式，也是我們為何是取倒數第二個漸近分數$\left ( \frac{P_{k-1}}{Q_{k-1}} \right )$的原因。


1.3 連分數的第k個漸近分數(the kth convergent of continued fraction)
$\left [ q_{1},q_{2},...,q_{k} \right ] =\frac{P_{n}}{Q_{n}}\left ( 1\leq k\leq n \right )$ 稱為有限簡單連分數 $\left [ q_{1},q_{2},...,q_{n} \right ]$ 的第 $k$ 個漸近分數(the kth convergent of $\left [ q_{1},q_{2},...,q_{n} \right ]$)。

有限連分數的一些性質，可參考林聰源的網頁。
http://episte.math.ntu.edu.tw/articles/mm/mm_02_3_08/page3.html

證明了 $P_k=q_kP_{k-1}+p_{k-2}$ 和 $Q_k=q_kQ_{k-1}+Q_{k-2}$ 這兩條式子後，接著再證明相鄰兩個漸近分數的差 $\delta _k-\delta _{k-1}=\frac{{-1}^k}{Q_kQ_{k-1}}$ ，最後得到 $aQ_{n-1}-bP_{n-1}+(-1)^{n-1}=0$。

關於 $P_k=q_kP_{k-1}+p_{k-2}$ 及 $Q_k=q_kQ_{k-1}+Q_{k-2}$ 這兩條式子，他們的用途是求漸進分數的分子及分母，顯然這兩條式子是遞迴式，稱為「Wallis-Euler recurrence relations」。我們用下面的表格示意。

以 $\frac{127}{52}=2+\frac{1}{2+\frac{1}{3+\frac{1}{1+\frac{1}{5}}}}=[2,2,3,1,5]$ 為例。

表一

表一清楚地列出如何透過 $P_k=q_kP_{k-1}+p_{k-2}$ 及 $Q_k=q_kQ_{k-1}+Q_{k-2}$，得到漸近分數。對於 $\delta _1$，分子 $P_1$ 就是 $q_{1}P_0+P_{-1}=2\times 1+0=2$，分母 $Q_1=q_1Q_0+Q_{-1}=2\times 0+1=1$。透過這個模式，我們可以得到完整的內容，見表二。

表二

表二清楚地列出每一個漸近分數的成分。其中最後一項 $\delta _5=\frac{P_5}{Q_5}=\frac{127}{52}$。

觀察漸近分數與原本的分數 $\frac{a}{b}$，我們可以發現下面的大小關係。

                        $\delta _1=[q_1]=q_1=\frac{P_1}{Q_1}<\frac{a}{b}$.
                        $\delta _2=[q_1,q_2]=q_1+\frac{1}{q_2}=\frac{P_2}{Q_2}>\frac{a}{b}$.
                        $\delta _3=[q_1,q_2,q_3]=q_1+\frac{1}{q_2+\frac{1}{q_3}}=\frac{P_3}{Q_3}<\frac{a}{b}$.
                        $\delta _4=[q_1,q_2,q_3,q_4]=q_1+\frac{1}{q_2+\frac{1}{q_3+\frac{1}{q_4}}}=\frac{P_4}{Q_4}>\frac{a}{b}$.

我們在數線上標示這些漸近分數的位置，如圖一。

圖一

從圖一可以看出，漸近分數會是以左右來回逼近 $\frac{a}{b}$ 的模式運作，最終收斂到中心點 $\frac{a}{b}$。奇數項在左側，偶數項在右側，其中奇數項會不斷地朝右方逼近(嚴格遞增)；偶數項則是不斷地朝左逼近(嚴格遞減)。以數學式表示如下。

$\delta _1<\delta _3<\cdots <\delta _{2k-1}<\frac{a}{b}<\delta _{2k}<\cdots <\delta _4<\delta _2$.

備註：有些書對於漸近分數的表示的足碼(index)是從 $0$ 開始，如此一來，其漸近分數偶數項會在左側，奇數項會在右側。

證明1：兩個漸近分數的差 $\delta _k-\delta _{k-1}=\frac{(-1)^k}{Q_kQ_{k-1}}$，$k\geq 2$。

<pf> 根據定義，$\delta_k=\frac{P_k}{Q_k}$，$\delta_{k-1}=\frac{P_{k-1}}{Q_{k-1}}$，所以$\delta _k-\delta _{k-1}=\frac{P_k}{Q_k}-\frac{P_{k-1}}{Q_{k-1}}=\frac{P_kQ_{k-1}-Q_kP_{k-1}}{Q_kQ_{k-1}}$.

                   分子 $=P_{k}Q_{k-1}-Q_{k}P_{k-1}=(q_kP_{k-1}+P_{k-2})Q_{k-1}-(q_kQ_{k-1}+Q_{k-2})P_{k-1}$
                                      $=(q_kP_{k-1}Q_{k-1})+P_{k-2}Q_{k-1}-(q_kQ_{k-1}P_{k-1})-Q_{k-2}P_{k-1}$
                                      $=-(P_{k-1}Q_{k-2}-Q_{k-1}P_{k-2})$.

觀察 $P_{k}Q_{k-1}-Q_{k}P_{k-1}$ 和 $-(P_{k-1}Q_{k-2}-Q_{k-1}P_{k-2})$，我們發現後者可以從原式中的 $k$ 用 $k-1$ 代替而得到。依此類推，我們會得到一連串的等式：

                             $\frac{P_{k-1}}{Q_{k-1}}=-(1)(P_{k-1}Q_{k-2}-Q_{k-1}P_{k-2})$
                                 $=(-1)^2(P_{k-2}Q_{k-3}-Q_{k-2}P_{k-3})$
                                 $\vdots$
                                 $=(-1)^{k-2}(P_{2}Q_{1}-Q_{2}P_{1})$

由於 $\delta _1=[q_1]=q_1=\frac{P_1}{Q_1}$，$\delta _2=[q_1,q_2]=q_1+\frac{1}{q_2}=\frac{P_2}{Q_2}$，我們知道 $P_1$、$P_2$、$Q_1$ 及 $Q_2$ 的值。

$\left\{\begin{matrix}P_1=q_1\\ Q_1=1\\ P_2=q_1q_2+1\\ Q_2=q_2\end{matrix}\right.$

因此分子 $\frac{P_{k-1}}{Q_{k-1}}=(-1)^{k-2}(P_{2}Q_{1}-Q_{2}P_{1})=(-1)^{k-2}\left [ (q_1q_2+1)\cdot 1-q_2(q_1) \right ]=(-1)^{k-2}=(-1)^k$，於是

$\delta _k-\delta _{k-1}=\frac{P_k}{Q_k}-\frac{P_{k-1}}{Q_{k-1}}=\frac{P_kQ_{k-1}-Q_kP_{k-1}}{Q_kQ_{k-1}}=\frac{(-1)^k}{Q_kQ_{k-1}}$。$\blacksquare$

若將證明1的 $\delta _k-\delta _{k-1}=\frac{(-1)^k}{Q_kQ_{k-1}}$ 等號兩邊同乘 $Q_kQ_{k-1}$，我們得到

$(\delta _k-\delta _{k-1})\cdot  Q_kQ_{k-1}=\left ( \frac{P_k}{Q_k}-\frac{P_{k-1}}{Q_{k-1}} \right )\cdot Q_kQ_{k-1}=P_kQ_{k-1}-Q_kP_{k-1}=(-1)^k$.

上式透露出 $P_k$ 與 $Q_k$ 是互質的(根據Bezout定理)，我們觀察表二也可發現到漸近分數一定是最簡分數。

證明1的結論也說明了兩個相鄰漸近的差會隨著漸近分數取得越準確($i$ 越大，$Q_i$也越大)而越小，再次觀察表二，結論確實如此。經過不斷地「左右震盪」，最終會到達 $\frac{a}{b}$。

證明2：兩個漸近分數的差 $\delta _k-\delta _{k-2}=\frac{(-1)^{k-1}}{Q_kQ_{k-2}}$，$k\geq 3$。

證明1中我們證明了兩個相鄰漸近分數的差會逐漸縮小。證明2是說明同側(參照圖一，在$\frac{a}{b}$的左側或右側)的漸近分數隨著足碼($k$)取得越大，左側(足碼為奇數)的漸近分數會越大，右側(足碼為偶數)的漸近分數會越小(Monotonicity properties of convergents.)。

<pf> $\delta _k-\delta _{k-2}=\frac{P_k}{Q_k}-\frac{P_{k-2}}{Q_{k-2}}$
            $=\frac{P_kQ_{k-2}-P_{k-2}Q_k}{Q_kQ_{k-2}}$
            $=\frac{\left ( q_kP_{k-1}+P_{k-2} \right )Q_{k-2}-P_{k-2}\left ( q_kQ_{k-1}+Q_{k-2} \right )}{Q_kQ_{k-2}}$
            $=\frac{\left ( q_kP_{k-1}Q_{k-2}+P_{k-2}Q_{k-2} \right )-\left ( q_kP_{k-2}Q_{k-1}+P_{k-2}Q_{k-2} \right )}{Q_kQ_{k-2}}$
            $=\frac{q_k(-1)^{k-1}}{Q_kQ_{k-2}}$ (since $P_kQ_{k-1}-Q_kP_{k-1}=(-1)^k$ by 證明1) $\blacksquare$

當足碼($k$)是奇數時，$\frac{q_k(-1)^{k-1}}{Q_kQ_{k-2}}$為正數；當足碼為偶數時，$\frac{q_k(-1)^{k-1}}{Q_kQ_{k-2}}$為負數。可參照圖一。

圖一

1.4 回顧 $127x-52y+1=0$
我們已經證明、也給出了關於一次不定方程的求解公式。現在再回頭看 $\frac{127}{52}$ 化為連分數的過程。

$\left\{\begin{matrix}(a=b\times q+r)\\127=52\times 2+23\\ 52=23\times 2+6\\ 23=6\times 3+5\\ 6=5\times 1+1\\ 5=1\times 5+0\end{matrix}\right.$.

透過不斷地代換(用下面的式子代換上一條式子)，我們得到：$-1=5\times 1-6=(23-6\times 3)-6$

                                                                                                                                              $=6\times (-4)+23$
                                                                                                                                              $=(52-23\times 2)\times (-4)+23$
                                                                                                                                              $=23\times 9 + (-52)\times 4$
                                                                                                                                              $=(127-52\times 2)\times 9 + (-52)\times 4$
                                                                                                                                              $=127\times 9 -52\times 22$

最後得到一組解 $(x_0,y_0)=(9,22)$。但是這種不斷替換的方法實在太累人了，不如套用上面的求解公式便捷。


2.1 無限簡單連分數(infinite simple continued fraction)
並非任何實數都能表示成有限簡單連分數, 例如 $\sqrt{2}$, $\pi$。

化成無限連分數的步驟：(1)Split (2)Flip (3)RAT(有理化)。可參考下面的影片(MathForKid65)。

所有的無理數都能用無限簡單連分數表示，且表示方式是唯一的(證明略)。

1770年，拉格朗日證明一個數字能表示成循環連分數，若且唯若此數為二次無理數(二次無理數是某些有理數係數的一元二次方程式的根)，例如下面影片的範例 $\sqrt{3}$，$\sqrt{3}$ 是方程式 $x^2-3=0$ 的根，所以 $\sqrt{3}$ 可表示成循環連分數。

一個計算線上連分數的網站：http://www.andrewduncan.ws/goldenratio/continuedfractions/

無限簡單連分數有許多與有限簡單連分數類似的性質。例如我們在1.3 連分數的第k個漸近分數(the kth convergent of continued fraction)中提到的遞迴關係式，也可套用至此，因為我們在推導過程並無使用到「有限步驟」的條件。