2013年12月31日 星期二

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


沒有留言:

張貼留言