[數論] 連分數(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. 非線性轉成線性, 變係數轉為常係數...等
• 母函數解法

[數論] 第一章第二節整理

• 一個數加上另一個數的整數倍後, 它們的最大公因數不變
• 輾轉相除法
• 最小公倍數
• 整值多項式(integral valued polynomial)不一定是整係數
• 整點(integral point), 或稱格點(lattice point)

定理1

假設 $a, b, c$ 是任意三個不全為零的整數, 並且 $a=bq+c$, 其中 $q$ 是整數, 則 $(a,b)=(b,c)$.

定理3

若 $a, b$ 是任意兩個正整數, 則存在兩個整數 $s, t$ 使得 $sa+tb=(a, b)$.

定理4

若 $a\mid bc$, $(a, b)=1$, 則 $a \mid c$.

定理9

若 $a, b$ 為正整數, $(a, b)=1$, 則 $[a, b]=ab$.

定理10

設  $a, b$ 為任意兩個正整數, 則 $[a, b]=\frac{ab}{(a, b)}$.

<pf> 令 $(a, b)=g$, $[a, b]=l$. $a=gh$, $b=gk$, $h,k\in \mathbb{Z}$, $(h, k)=1$. 則 $[a, b]=l=ghk$. $(a, b)[a, b]=g\cdot l=g\cdot ghk=gh\cdot gk=a\cdot b$.

定義3

當變數 $x$ 取整數時, 若多項式 $f(x)=a_{k}x^{k}+a_{k-1}x^{k-1}+...+a_{1}x+a_{0}$ 之值恆為整數, 則稱此多項式為整值多項式(integral valued polynomial). 整值多項式不一定是整係數的, 例如組合數.

公式：定義 $\Delta f(x)=f(x+1)-f(x)$, 則 $\Delta \binom{x}{k}=\binom{x+1}{k}-\binom{x}{k}=\binom{x}{k-1}$.

定理12
任何 $k$ 次整值多項式 $f(x)$ 必可表示為 $f(x)=C_{k}\binom{x}{k}+C_{k-1}\binom{x}{k-1}+...+C_{1}\binom{x}{1}+C_{0}$, 其中 $C_{k}, C_{k-1},..., C_{0}$ 皆為整數.

定理13
對任意整數 $x$, 整值多項式 $f(x)=C_{k}\binom{x}{k}+C_{k-1}\binom{x}{k-1}+...+C_{1}\binom{x}{1}+C_{0}$ 的值皆為 $m$ 的倍數的充分必要條件為 $m\mid \left ( C_{k}, C_{k-1},...,C_{0} \right )$.

定理14
設 $k$ 次多項式為 $f(x)=a_{k}x^{k}+a_{k-1}x^{k+1}+...+a_{0}, (a_{k}\neq 0)$, 若 $x$ 取 $k+1$ 個連續整數 $a, a+1, ..., a+k$ 的值恆為整數, 則 $f(x)$ 為整值多項式.

定理14'
設 $f(x)$ 為 $k$ 次多項式, 若 $x$ 取 $k+1$ 個連續整數 $a, a+1, ..., a+k$ 時, $f(x)$ 的值皆能被 $m$ 整除, 則對任意整數 $x$, $f(x)$ 皆能被 $m$ 整除.

定義4
平面上座標 $x, y$ 都是整數的點稱為整點(integral point)或格點(lattice point).

例1 對任何整數 $q$, 試證 $(a_{1} ,a_{2})=(a_{1}, a_{2}+a_{1}q)$, i.e., 一個數加上另一個數的整數倍後, 它們的最大公因數不變.

例6 試證：$f(n)=\frac{1}{3}n^{3}+\frac{1}{2}n^{2}+\frac{1}{6}n$ 是一個整值多項式.

例8 試證：$f(n)=n^{3}+\frac{3}{2}n^{2}+\frac{1}{2}n-1$ 對任意整數 $n$ 都是整數, 且 $3$ 除時餘 $2$.

例10 試求在方程 $x^{2}+y^{2}=625$ 的圖像的圓上有多少整點.

例11 試證：方程 $x^{2}-y^{2}=6$ 所畫出的雙曲線上沒有整點.

例12 設 $m$ 和 $n$ 為正整數. 試證：在平面內以 $(0,0), (n,0), (0,m)$ 為頂點的三角形中(包括三條邊上)整點的個數為 $M=\frac{1}{2}[(m+1)(n+1)+d+1], d=(m,n)$.

解答題
7. 試證：若 $(a,b)=1$, 則 $(a,bc)=(a,c)$.
9. 試證：$\left ( \frac{a_{1}}{\left ( a_{1},a_{2},...,a_{n} \right )},  \frac{a_{2}}{\left ( a_{1},a_{2},...,a_{n} \right )},..., \frac{a_{n}}{\left ( a_{1},a_{2},...,a_{n} \right )}\right )=1$.
11. 設 $n$ 是奇數, 試證：(1) 當 $n\geq 3$ 時, 一定存在正整數 $k\leq n-1$, 使得 $n\mid (2^{k}-1)$. (2) 必存在正整數 $t$, 使 $(2^{t}-3,n)=1$.
17. 試證：若 $(a,b)=1$, 則 $(d,ab)=(d,a)(d,b)$.
18. 設 $a>b>0, n>1$, 試證：$(a^{n}-b^{n})\nmid (a^{n}+b^{n})$.
19. 設 $a>b, (a,b)=1$, 試證：$(a^{m}-b^{m},a^{n}-b^{n})=a^{(m,n)}-b^{(m,n)}$.
25. 若 $(a,b)=1$, 試證：$(a+b,a^{2}+b^{2})=1$ 或 $2$.
27. 設 $m, n$ 是正整數且 $m$ 是奇數, 試證：$(2^{m}-1,2^{n}+1)=1$.
28. 設 $(m,n)=1$, 試證：$m!n!\mid (m+n-1)!$.
30. 設 $a, b, c$ 為任意三個整數, 且 $c\neq 0$, 試證：總能找到兩個互質的整數 $k, m$, 使得 $c\mid (ak+bm)$.
32. 當 $n$ 為什麼樣的正整數時, $n^{4}+n^{2}$可被 $2n+1$ 整除？
<pf> $n^{4}+n^{2}=\left ( 2n+1 \right )\left ( \frac{n^{3}}{2} \right )+\left ( -\frac{n^{3}}{2} +n^{2}\right )$. 因為餘數要為零, 所以 $\left ( -\frac{n^{3}}{2} +n^{2}\right )=0$, 算出 $n=0,0,2$. 又$n$ 是正整數, 故 $0$ 不合, 所以 $n=2$.
33. 已知正整數 $m>n$, 當 $4^{m}+4^{n}$ 為 $100$ 的倍數時, $m+n$ 最小為多少?
34. 若 $6\mid (a_{1}+a_{2}+a_{3})$, 試證：$6\mid (a_{1}^{3}+a_{2}^{3}+a_{3}^{3})$.
35. 若 $n$ 和 $A$ 是正整數, 且 $\sqrt[n]{A}$ 不是整數, 試證：$\sqrt[n]{A}$ 一定不是有理數.
36. 設 $a, b, c, d$ 為任意的四個整數, 試證：$12\mid (a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$.
39. 設 $a, b, c$ 是兩兩互素的正整數, 且 $\frac{1}{a}+\frac{1}{b}=\frac{1}{c}$, 試證：$a+b, a-c, b-c$ 都是平方數.
40. 試證：存在無窮多個 $n$, 使 $n\mid (2^{n}+1)$.
41. (1) 若 $n\mid (2^{n}+2), (n-1)\mid (2^{n}+1)$, 試證：當 $m=2^{n}+2$ 時, 恆有 $m\mid (2^{m}+2)$, $(m-1)\mid (2^{m}+1)$.
      (2) 試證：存在無窮多個 $n$, 使 $n\mid (2^{n}+2)$.
42. 若正整數 $a, b$ 滿足 $[a,b]=(a,b)$, 試證：$a=b$.
44. 設 $a, b, c$ 是正整數, 試證：(1) $[a, b, c](ab, bc, ca)=abc$; (2) $[a, b, c]=abc$ 的充分必要條件是 $(a, b)=(b,c)=(c,a)=1$.
45. 試證：$[a_{1},a_{2},...,a_{n}]=\frac{a_{1}a_{2}...a_{n}}{(A_{1},A_{2},...,A_{n})}$, $n\geq 2$, 其中 $A_{i}=\frac{a_{1}a_{2}...a_{n}}{a_{i}}, i=1,2,...,n$.
46. 試證：$(a,b,c)\leq (a,b)$, $[a,b,c]\geq [a,b]$.
47. 試求滿足 $(a,b)=10$, $[a,b]=100$ 的全部正整數組 $a, b$.
49. 試求滿足 $(a,b)=8$, $[a,b]=48$的全部正整數組 $a, b$.
54. 試證：對任何整數 $n$, 多項式 $f(n)=\frac{1}{5}n^{5}-\frac{2}{3}n^{3}-\frac{8}{15}n$ 皆取整數值.
57. 試求能整除 $f(n)=n^{3}+5n$ 的一切整數, 並確定其中的最大者.
58. 試證：對任何整數 $n$, $7\mid (n^{7}+6!n)$. (試用費馬定理)
59. 設 $f(x)$ 為整係數多項式, 對於整數 $x_{0}$, $a$, 當 $f(a)\neq 0$ 時, 試證：$x_{0}-a$ 整除 $f(x_{0})$ 的充分條件是 $x_{0}-a$ 整除 $f(a)$.
60. 試求最大的正整數 $n$, 使 $n^{3}+100$ 能被 $n+10$ 整除.
61. 試求使 $n^{3}+m^{2}$ 能被 $n+m$ 整除的正整數 $n$ 的最大值.
62. 設有整係數 $k$ 次多項式 $f(x)$ 與一次多項式 $ax-b$ ($a\neq 1, (a,b)=1$), 試證：整數 $x_{0}$ 使 $ax_{0}-b$ 整除 $f(x_{0})$ 的充分必要條件是 $(ax_{0}-b)\mid a^{k}f\left ( \frac{b}{a} \right )$.
63. 已知 $n$ 是正整數, 且 $n^{2}-71$ 能被 $7n+55$ 整除, 試求 $n$.
64. 當 $n$ 是何正整數時, $2n+1$ 整除 $n^{4}+n^{2}$？
65. 設 $m_{1}, m_{2}, n_{1}, n_{2}$ 都是整數, 且 $m_{1}\neq m_{2}$, 試證：存在一個整係數多項式 $f(x)$ 滿足 $f(m_{1})=n_{1}$, $f(m_{2})=n_{2}$ 的充分必要條件是 $(m_{1}-m_{2})\mid (n_{1}-n_{2})$.
66. 若整數 $b$ 為整係數多項式 $f(x)$ 的根, 即 $f(b)=0$, 試證：對任意整數 $a$, 有 $(a-b)\mid f(a)$.
67. 試證：任何整係數多項式 $f(x)$ 都不能同時滿足 $f(7)=5$, $f(15)=9$.

[數論] 第一章第一節整理

參考資料

張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493

• 數學歸納法(mathematical induction)
• 二項式公式(binomial formula)：連續 $k$ 個整數的乘積能被 $k!$ 整除
• 數的奇偶性(odevity)

定義1
設 $a$, $b$ 是任意兩個整數, 其中 $b\neq 0$, 若存在一個整數 $q$ 使得等式 $a= bq$ 成立, 則稱 $a$ 是 $b$ 的倍數(multiple), $b$ 是 $a$ 的因數(divisor), 記作 $b\mid a$.

1. 若 $b\mid a$, 則有 $b\mid -a$, $-b\mid a$, $\left | b \right |\mid \left | a \right |$
2. 若 $b\mid a$, $c\mid b$, 則 $c\mid a$
3. 若 $b\mid a$, 則對任何整數 $m$, 有 $b\mid ma$
4. 若 $b\mid a_{1}$, $b\mid a_{2}$, 則對任何整數 $m_{1}$, $m_{2}$, 有 $b\mid \left ( m_{1}a_{1}+m_{2}a_{2} \right )$
5. 若 $b\mid a$ 且 $a\mid b$, 則 $a=\pm b$
6. 若 $b\mid a$ 且 $a\neq 0$, 則 $\left | b \right |\leq \left | a \right |$

定理1 (除法定理(division algorithm))
設 $a$, $b$ 是兩個整數, 其中 $b>0$, 則存在兩個唯一的整數 $q$ 和 $r$, 使得 $a=bq+r$, $0\leq r<b$.

例1 試證：若 $3\mid n$ 且 $7\mid n$, 則 $21\mid n$.
例2 設 $a$, $b$ 是兩個非零整數, 且有整數 $x$, $y$, 使得 $ax+by=1$. 試證：若 $a\mid n$ 且 $b\mid n$, 則 $ab\mid n$.
例3 試證：對任何非負整數 $n$, $f\left ( n \right )=10^{n}+18n-28$ 都是$27$的倍數.
例4 設 $n\neq 1$, $k\geq 1$. 試證 $\left ( n-1 \right )^{2}\mid \left ( n^{k}-1 \right )$ 的充分必要條件是 $\left ( n-1 \right )\mid k$.
例5 試證：若 $5\mid \left ( a+b \right )$, 則 $25\mid \left ( a^{5}+b^{5} \right )$.
例10 若正整數 $n$ 的各位數碼之和與 $2n$ 的各位數碼之和相等, 試證： $n$ 必能被 $9$ 整除.
例11 設一個六位數 $n$, 它的前三位數碼組合的數 $a$ 與它後三位數碼組成的數 $b$ 之差 $b-a$ 能被 $7$ 整除, 試證：$7\mid n$.
例12 求能被自己的數碼之積整除的所有兩位數.
例13 試證：整數 $n^{5}$ 的個位數(即末位數碼)與 $n$ 的個位數是相同的.

解答題
7. 試證：若 $\left ( m-a \right )\mid \left ( mn+ab \right )$, 則 $\left ( m-a \right )\mid \left ( mb+na \right )$.
16. 試證：對任何正整數 $n$, $\left ( 3+\sqrt{5} \right )^{n}+\left ( 3-\sqrt{5} \right )^{n}$ 恆為整數且能被 $2^{n}$ 整除.
19. 試證：超過 $\left ( \sqrt{3}+1 \right )^{2n}$ 的最小整數可被 $2^{n+1}$ 整除.
20. 若 $a$, $b$ 為正整數, $a^{n}\mid b$, 試證：$a^{n+1}\mid \left ( a+b \right )^{b}-1$, $n=0,1,2,...$.
29. 試證： $3^{n}+1$ 能被 $2$ 或 $2^{2}$ 整除, 而不能被 $2$ 的更高次冪整除.
30. 試證：對於任何正整數 $n$ 和 $k$, 數 $N=2n^{3k}+4n^{k}+10$ 都不能表示為若干個連續正整數的乘積.
33. 試證：形如 $2^{k}$($k$ 為正整數)的數不能是幾個連續正整數的和.
<pf> 假設 $2^{k}$ 可以表示成連續 $n$ 個正整數的和, 亦即 $2^{k}=a_{1}+a_{2}+...+a_{n}=\frac{[a_{1}+a_{n}]n}{2}$. 上式可改寫為 $2^{k+1}=[a_{1}+a_{n}]n$. 如果 $n$ 是偶數, 則 $[a_{1}+a_{n}]$ 為奇數, 表示 $[a_{1}+a_{n}]n$ 含有 $2$ 以外的質因數, 無法表示成單純的 $2$ 的次方, 與原本的假設矛盾; 反之, 若 $n$ 是奇數, $[a_{1}+a_{n}]n$ 一樣含有 $2$ 以外的質因數. 所以原命題成立.
35. 若 $n>1$, 試證 $\underset{n}{\underbrace{11...1}}$ 不是整數的平方.
36. 有 $n$ 個數 $a_{1},a_{2},...,a_{n}$, 它們中的每一個數均為 $+1$ 或 $-1$, 若 $a_{1}a_{2}+a_{2}a_{3}+...+a_{n-1}a_{n}+a_{n}a_{1}=0$, 試證 $n$ 是 $4$ 的倍數.
<pf> 對每個 $a_{i}a_{j}$ 而言, $a_{i}a_{j}$ 不是 $1$ 就是 $-1$, 若有 $k$ 個 $-1$, 表示也同樣有 $k$ 個 $1$, 所以總數 $n=2k$. 若 $a_{i}a_{j}=1$, 表示 $a_{i}=a_{j}=1$ 或 $a_{i}=a_{j}=-1$, 兩數皆為同號; 若 $a_{i}a_{j}=-1$, 表示兩數為異號.
從起始的 $a_{1}a_{2}$ 到最後的 $a_{n}a_{1}$, 中間有 $k$ 個 $-1$, 表示從 $a_{1}$ 開始, 中間歷經了 $k$ 次變號. 若經歷奇數次變號,  $a_{1}a_{2}$ 的 $a_{1}$ 和 $a_{n}a_{1}$ 的 $a_{1}$ 的正負符號會不一樣. 所以經歷的變號次數為偶數次, 亦即 $k$ 為偶數, 所以 $n=2k$ 是 $4$ 的倍數.
37. 試證：若正整數 $n$ a_{i}a_{j}可以寫成兩個整數的平方和, 則 $2n$ 也可以寫成兩個整數的平方和, 反之亦然.
39. 試證：對任何整數 $n$, 下述的方程式無整數解：$x^{2}-y^{2}=4n+2$.
40. 若 $n$ 為正整數, 但不是 $4$ 的倍數, 試證：$5\mid \left (1^{n}+2^{n}+3^{n}+4^{n} \right )$.
<pf> 可用末位數是否為 $0$ 或 $5$ 去判斷. 會發現末位數字以四個數字為一循環，依序是 $0$, $0$, $0$ 及 $4$.
41. 有 $n$ 個整數, 其積為 $n$, 其和為 $0$, 試證：$4\mid n$.
42. 設整數 $a>0$, $b>2$, 試證：$(2^{b}-1)\nmid  (2^{a}+1)$.
<pf> 假設 $a>b$, $(2^{a}+1,2^{b}-1)=\left (  2^{a}+1+(1)(2^{b}-1),2^{b}-1\right )=(2^{a}+2^{b},2^{b}-1)$, 因為 $2^{a}+2^{b}$ 是偶數, $2^{b}-1$ 是奇數, 故 $(2^{a}+2^{b},2^{b}-1)=1$, 表示 $2^{a}+1$ 和 $2^{b}-1$ 兩數互質. 同理, 當 $a<b$ 時, 一樣得到 $2^{a}+1$ 和 $2^{b}-1$ 兩數互質的結論.
當 $a=b$ 時, $(2^{a}+1,2^{b}-1)=(2^{a}+1,2^{a}-1)=\left ( 2^{a}+1+(-1)(2^{a}-1),2^{a}-1 \right )=(2,2^{a}-1)=1$, $2^{a}+1$ 和 $2^{b}-1$ 仍為互質.
因為兩數互質, 故一數必不為另一數的倍數.
44. 若正整數 $n>1$, 試證：(1) $2^{n}-1$ 不是任何整數的平方 (2) $2^{n}-1$ 不是任何整數的立方.
46. 若 $k$ 是正奇數, 試證：對任何正整數 $n$, 有 $(1+2+3+\cdots +n)\mid (1^k+2^k+3^k+\cdots n^k)$.
47. (1) 試求出所有的正整數 $n$, 使 $2^{n}-1$ 能被 $7$ 整除.
49. 是否存在 $2n$ 個正奇數的倒數之和等於 $1$?
50. 試證：對於任意的正整數 $n$, 一定存在 $n$ 的一個倍數 $m$, 它是僅由數字 $0$ 和 $1$ 組成的.
51. 任給 $7$ 個不同的整數, 試證：必有兩個整數, 其和或差是 $10$ 的倍數.
52. 任給 $n+1$ 個不同的整數, 且它們都小於 $2n$, 試證：必可從中選出三個數, 使其中兩個之和等於第三個.
53. 將 $1,2,\cdots ,10$ 這 $10$ 個數任何擺成一個圈圈(即放在一個圓周上), 試證：必有 $3$ 個相鄰的數, 它們的和不小於 $17$
54. 設正整數 $n$ 有如下的性質：從 $1,2,,\cdots ,n$ 中任取 $50$ 個不同的數, 這 $50$ 個數中必有兩個數之差等於 $7$. 試求 $n$ 的最大值.
55. 從 $1,2,3,\cdots ,100$ 這 $100$ 個正整數中, 隨意選出 $51$ 個數, 試證：其中一定有兩個數, 它們之中的一個可以整除另一個.
56. 試證：$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}\left ( n>1 \right )$ 不是整數.
<pf> 在分母中找出含因數$2$最多個的數, 令其為 $2^{m}$. 令 $t$ 為所有不大於 $n$ 之奇數的乘積. 原式乘上 $2^{m-1}t$ 後,  其中 $\frac{1}{2^{m}}\cdot 2^{m-1}t$ 為 $\frac{1}{2}t$, 其餘各項皆為整數. 由於整數乘上整數後仍為整數, 但今乘上 $2^{m-1}t$ 後卻不為整數, 故原式非整數
57. 試證：$\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\cdots +\frac{1}{2n+1}(n\geq 1)$ 不是整數.

解答 https://drive.google.com/folderview?id=0ByvpOhgGXKImNldGZVlsdG1ORzQ&usp=sharing

[數論] p58, 第一章第二節, Q17

17. 試證：若 $\left ( a,b \right )=1$, 則 $\left ( d,ab \right )=\left ( d,a \right )\left ( d,b \right )$

證：
$\left ( d,ab \right )=\left ( d,a \right )\left ( \frac{d}{\left ( d,a \right )},\frac{ab}{\left ( d,a \right )} \right )=\left ( d,a \right )\left ( \frac{d}{\left ( d,a \right )},b \right )=\left ( d,a \right )\left ( d,b \right )$

註：

1. 若 $a,b$ 是任意兩個不全為零的整數, $m$ 是任一正整數, 則 $\left ( am,bm \right )=\left ( a,b \right )m$
2. 若 $\left ( a,b \right )=1$, 則 $\left ( a,bc \right )=\left ( a,c \right )$.

$\because \left ( \frac{d}{\left ( d,a \right )},\frac{a}{\left ( d,a \right )} \right )=1$, $\therefore \left ( \frac{d}{\left ( d,a \right )},\frac{ab}{\left ( d,a \right )} \right )=\left ( \frac{d}{\left ( d,a \right )},b \right )$

$\because \left ( \left ( d,a \right ),b \right )=\left ( d,\left ( a,b \right ) \right )=\left ( d,1 \right )=1$, $\therefore \left ( \frac{d}{\left ( d,a \right )},b \right )=\left ( \frac{d}{\left ( d,a \right )}\left ( d,a \right ),b \right )=\left ( d,b \right )$