[數論] 連分數(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)中提到的遞迴關係式，也可套用至此，因為我們在推導過程並無使用到「有限步驟」的條件。

[數論] 遞迴數列解法

參考資料：
遞歸數列，凡異出版社，1994年3月初版，ISBN：957694130X
線性遞迴關係之求解(下) - 中研院數學研究所

二階常係數線性齊次遞迴方程的解法(單一方程)
對於 $a_{n}+p_{1}a_{n-1}+p_{2}a_{n-2}=0$, 通解的主要思路是通過用 $a_{n}=x^{n}$ 代換, 把上述方程轉化到特徵方程 $x^{2}+p_{1}x+p_{2}=0$, 解此特徵方程即得原方程的通解. 最後把初始條件帶入通解, 得到特解.

• 當 $\Delta >0$ 時, 有兩相異實根, $x_{1}=q_{1}$, $x_{2}=q_{2}$

        通解為 $a_{n}=c_{1}q_{1}^{n}+c_{2}q_{2}^{n}$.

• 當 $\Delta =0$ 時, 有兩相等實根, $x_{1}=x_{2}=q$

        通解為 $a_{n}=\left ( c_{1}+c_{2}n \right )q^{n}$.

• 當 $\Delta <0$ 時, 有一對共軛複數根, $x_{1}=r\left ( cos\theta +isin\theta  \right )$, $x_{2}=r\left ( cos\theta -isin\theta  \right )$

        通解為 $a_{n}=a_{n}=r^{n}\left ( c_{1}cosn\theta +c_{2}sinn\theta  \right )$.

遞迴方程組的解法
設有兩個數列 $a_{1},a_{2},...a_{n},...$ 和 $b_{1},b_{2},...b_{n},...$ 同時滿足遞迴方程組 $\left\{\begin{matrix}
a_{n+1} =p_{1}a_{n}  +q_{1}b_{n} \\
b_{n+1} =p_{2}a_{n}  +q_{2}b_{n}
\end{matrix}\right.$, 其中 $p_{i}$, $q_{i}(i=1,2)$ 是實常數. 這個遞迴方程組稱為二元遞迴方程組.

• 代入消去法

• 行列式法

        對於方程組 $\left\{\begin{matrix}a_{n+1}=p_{1}a_{n}+q_{1}b_{n}\\ b_{n+1}=p_{2}a_{n}+q_{2}b_{n}\end{matrix}\right.$, 若 $\begin{vmatrix}p_{1} &q_{1} \\ p_{2} &q_{2} \end{vmatrix}=0$, 即 $p_{1}=\lambda p_{2}$, $q_{1}=\lambda q_{2}$.

        對於 $\begin{vmatrix}p_{1} &p_{2} \\ q_{1} &q_{2} \end{vmatrix}\neq 0$, 我們求形如 $a_{n}=Ax^{n}$, $b_{n}=Bx^{n}$ 的解($A$, $B$ 為待定係數).

二階常係數線性非齊次遞迴方程的解法
若存在兩個常數 $p_{1}$, $p_{2}$, 對任意 $n\geq 2$, 有 $a_{n}+p_{1}a_{n-1}+p_{2}a_{n-2}=f(n)$, 其中 $f(n)\neq 0$, 則稱此方程為「二階常係數線性非其次遞迴方程」, 對應之齊次特徵方程為 $x^{2}+p_{1}x+p_{2}=0$

通解 = 對應的齊次方程的通解 + 非齊次方程的任何一個特解

就 $f(n)$ 的幾種特殊類型函數, 我們討論它的特解形式. 以下列出六種：

• $f(n)$ 是 $n$ 的二次多項式, 即 $f(n)=a_{2}n^{2}+a_{1}n+a_{0}$

       (1) 若 $x=1$ 不是特徵方程的根, 則特解為 $a_{n}^{*}=A_{2}n^{2}+A_{1}n+A_{0}$.

       把特解代入特徵方程式, 比較係數得到 $\left\{\begin{matrix}A_{2}\left ( 1+p_{1}+p_{2} \right )=a_{2}\\ A_{1}\left ( 1+p_{1}+p_{2} \right )-2A_{2}\left ( p_{1}+2p_{2} \right )=a_{1}\\ A_{0}\left( 1+p_{1}+p_{2} \right )-A_{1}\left ( p_{1}+p_{2} \right )+A_{2}\left ( p_{1}+4p_{2} \right )=a_{0}\end{matrix}\right.$

       因為 $x=1$ 不是 $x^{2}+p_{1}x+p_{2}=0$ 的根, 即 $1+p_{1}+p_{2}\neq 0$, 故 $A_{2}$, $A_{1}$ 和 $A_{0}$ 都可以確定.

       (2) 若 $x=1$ 是特徵方程式的單根, 則特解為 $a_{n}^{*}=n\left ( A_{2}n^{2}+A_{1}n+A_{0} \right )$.

       (3) 若 $x=1$ 是特徵方程式的重根, 則特解為 $a_{n}^{*}=n^{2}\left ( A_{2}n^{2}+A_{1}n+A_{0} \right )$.

• $f(n)$ 是指數函數, 即 $f(n)=c\cdot k^{n}$

       (1) 若 $x=k$ 不是特徵方程式的根 則特解為 $a_{n}^{*}=Bk^{n}$. ($B$ 是待解係數)

       (2) 若 $x=k$ 是特徵方程式的單根 則特解為 $a_{n}^{*}=nBk^{n}$.

       (3) 若 $x=k$ 是特徵方程式的重根 則特解為 $a_{n}^{*}=n^{2}Bk^{n}$.

• $f(n)$ 是正弦或餘弦函數, 即 $f(n)=c\cdot cosn\theta $ 或 $f(n)=c\cdot sinn\theta $
• $f(n)$ 是一個指數函數與多項式的積, 即 $f(n)=g(n)\cdot k^{n}$, 其中 $k$ 是常數, $g(n)$ 是關於 $n$ 的 $m$ 次多項式
• $f(n)$ 是指數函數與正弦(或餘弦)函數的積, 即 $f(n)=k^{n}cosn\theta $ 或 $f(n)=k^{n}cosn\theta $
• $f(n)$ 是多項式與正弦(或餘弦)函數的積, 即 $f(n)=g(n)cosn\theta $ 或 $f(n)=g(n)sinn\theta $

二階遞迴數列的求和問題

一般來說, 數列 $\left \{ a_{n} \right \}$ 的求和問題, 關鍵是找出其通項公式再求和. 但是, 對於遞迴數列, 我們可以不求出它的通項, 直接從它所適合的遞迴方程中求出這個遞迴數列的前 $n$ 項的和.

假設數列  $\left \{ a_{n} \right \}$ 是二階遞迴列, 所適合的二階線性齊次遞迴方程為 $f(x)=0$(二次多項式), 則 $\left \{ a_{n} \right \}$ 的前 $n$ 項和 $S_{n}$ 對應之特徵方程是 $(x-1)f(x)=0$, 它只比 $\left \{ a_{n} \right \}$ 的特徵方程多了一個特徵根 $x=1$.
(hint: 用 $a_{n}=S_{n}-S_{n-1}(n\geq 2)$ 代換)

遞迴方程的其他各種解法
當特徵方程式的根不易求出, 或遞迴方程不是線性或常係數時, 需要透過其他的途徑求解.

• 數學歸納法
• 迭代法與逐差法
• 變量代換法(換元法) e.g. 非線性轉成線性, 變係數轉為常係數...等
• 母函數解法