互除法から連分数へ

任意の整数$a \in \mathbb{Z}$に対して
$$ \gcd(a,0) = |a|$$
が成り立つ．

$39$と$28$との最大公約数は（明らかに）$1$である：
\begin{align} 39 &= 1 \cdot 28 + 11;\\ 28 &= 2 \cdot 11 + 6;\\ 11 &= 1 \cdot 6 + 5;\\ 6 &= 1 \cdot 5 + 1;\\ 5 &= 5 \cdot 1 + 0. \end{align}
また，
$$ \begin{bmatrix} 0 & 1 \\ 1 & -5 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & -2 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix} = \begin{bmatrix} -5 & 7 \\ 25 & -35 \end{bmatrix}$$
より，
$$ 39 \cdot (-5) + 28 \cdot 7 = 1$$
を得る．

分数$\frac{A_{1}}{B_{1}},\frac{A_{2}}{B_{2}},\frac{A_{3}}{B_{3}} \in \mathbb{R}$を計算してみると，
\begin{align} \frac{A_{1}}{B_{1}} &= \frac{q_{0}}{1} = q_{0};\\ \frac{A_{2}}{B_{2}} &= \frac{A_{1}q_{1}+A_{0}}{B_{1}q_{1}+B_{0}} = \frac{q_{0}q_{1} + 1}{q_{1}} = q_{0} + \frac{1}{q_{1}};\\ \frac{A_{3}}{B_{3}} &= \frac{A_{2}q_{2}+A_{1}}{B_{2}q_{2}+B_{1}} = \frac{(q_{0}q_{1} + 1)q_{2} + q_{0}}{q_{1}q_{2} + 1} = q_{0} + \frac{q_{2}}{q_{1}q_{2}+1} = q_{0} + \cfrac{1}{q_{1} + \cfrac{1}{q_{2}}};\\ \end{align}
となる．

1次分数変換
$$ \begin{bmatrix} \alpha & \beta \\ \gamma & \delta \end{bmatrix} \colon \mathbb{R} \cup \{\infty\} \to \mathbb{R} \cup \{\infty\};\ x \mapsto \frac{\alpha x + \beta}{\gamma x + \delta} \eqqcolon \begin{bmatrix} \alpha & \beta \\ \gamma & \delta \end{bmatrix} \star x$$
を用いると，
\begin{align} [q_{0};q_{1},\ldots,q_{n-2},q_{n-1}] &= \frac{A_{n}}{B_{n}} \\ &= \begin{bmatrix} A_{n} & A_{n-1} \\ B_{n} & B_{n-1} \end{bmatrix} \star \infty \\ &= \begin{bmatrix} q_{0} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} q_{1} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} q_{n-2} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} q_{n-1} & 1 \\ 1 & 0 \end{bmatrix} \star \infty \\ &= \begin{bmatrix} q_{0} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} q_{1} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} q_{n-2} & 1 \\ 1 & 0 \end{bmatrix} \star q_{n-1} \end{align}
と書ける．

$d \coloneqq \gcd(a,b) \neq 0$のとき，（$n \geq 2$とすると）
$$ \begin{bmatrix} a/d \\ b/d \end{bmatrix} = \begin{bmatrix} q_{0} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} q_{n-2} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} q_{n-1} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} q_{0} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} q_{n-2} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} q_{n-1} \\ 1 \end{bmatrix}$$
であり，lin-frac-transfより
$$ \frac{a}{b} = \frac{a/d}{b/d} = [q_{0};q_{1},\ldots,q_{n-2},q_{n-1}] = \begin{bmatrix} q_{0} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} q_{n-2} & 1 \\ 1 & 0 \end{bmatrix} \star q_{n-1}$$
となるので，この最右辺を計算することによって，有理数$a/b$の既約分数表示が得られる．たとえば$11178/16419$の場合，
\begin{align} 11788 &= 0 \cdot 16419 + 11788;\\ 16419 &= 1 \cdot 11788 + 4631;\\ 11788 &= 2 \cdot 4631 + 2526;\\ 4631 &= 1 \cdot 2526 + 2105;\\ 2526 &= 1 \cdot 2105 + 421;\\ 2105 &= 5 \cdot 421 + 0; \end{align}
より，
$$ \frac{11788}{16419} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \star 5 = \begin{bmatrix} 5 & 3 \\ 7 & 4 \end{bmatrix} \star 5 = \frac{5 \cdot 5 + 3}{7 \cdot 5 + 4} = \frac{28}{39}$$
と計算できる．

$d \coloneqq \gcd(a,b) \neq 0$のとき，
$$ \begin{bmatrix} a' \\ b' \end{bmatrix} \coloneqq \begin{bmatrix} q_{0} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} q_{n-2} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \quad\leadsto\quad \frac{a'}{b'} = [q_{0};q_{1},\ldots,q_{n-2}]$$
とおくと，
$$ \begin{bmatrix} a/d & a' \\ b/d & b' \end{bmatrix} = \begin{bmatrix} q_{0} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} q_{n-1} & 1 \\ 1 & 0 \end{bmatrix}$$
であるから，両辺のディターミナントを取って
$$ \frac{a}{d}b' - a'\frac{b}{d} = (-1)^{n} \quad\leadsto\quad a \cdot (-1)^{n}b' + b \cdot (-1)^{n+1}a' = d$$
を得る（cf. euclid）．たとえば，$(a,b) = (28,39)$のとき，上例より
$$ \frac{28}{39} = [0;1,2,1,1,5],\ [0;1,2,1,1] = [0;1,2,2] = \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{2}}} = \cfrac{1}{1 + \cfrac{2}{5}} = \frac{5}{7}$$
となるので，
$$ 28 \cdot 7 - 39 \cdot 5 = 1$$
を得る（cf. 3928）．

任意の$n \in \mathbb{Z}_{\geq 2}$に対して
$$ A_{n}B_{n-1}-A_{n-1}B_{n} = (-1)^{n} \quad\leadsto\quad \frac{A_{n}}{B_{n}} - \frac{A_{n-1}}{B_{n-1}} = \frac{(-1)^{n}}{B_{n-1}B_{n}}$$
が成り立つので，
\begin{align} \frac{A_{n}}{B_{n}} &= \frac{A_{n-1}}{B_{n-1}} + \frac{(-1)^{n}}{B_{n-1}B_{n}} \\ &= \frac{A_{n-2}}{B_{n-2}} + \frac{(-1)^{n-1}}{B_{n-2}B_{n-1}} + \frac{(-1)^{n}}{B_{n-1}B_{n}} \\ &= \cdots \phantom{\frac{A}{B}}\\ &= \frac{A_{1}}{B_{1}} + \sum_{k=2}^{n} \frac{(-1)^{k}}{B_{k-1}B_{k}} \end{align}
を得る．よって
$$ [q_{0};q_{1},q_{2},\ldots{}] = q_{0} + \sum_{k=2}^{\infty} \frac{(-1)^{k}}{B_{k-1}B_{k}} = q_{0} + \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{B_{n}B_{n+1}}$$
が成り立つ．

整数列$(0,1,1,\ldots{}) \in \mathcal{Q}$から定まる整数列$B_{\bullet}$はFibonacci数列$F_{\bullet}$に外ならない（cf. Bn-posiの証明）：
$$ F_{0} = 0,\ F_{1} = 1,\ F_{n+2} = F_{n+1} + F_{n}.$$
したがって
$$ \lambda \coloneqq [0;1,1,\ldots{}] = \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{F_{n}F_{n+1}}$$
が成り立つ．ところで，
$$ 0 = \frac{A_{1}}{B_{1}} < \lambda \quad\leadsto\quad \frac{1}{\lambda} = [1;1,1,\ldots{}] = 1 + \lambda$$
であるから，$\lambda$について解いて
$$ \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{F_{n}F_{n+1}} = \lambda = \frac{-1+\sqrt{5}}{2}$$
を得る．また，$A_{\bullet+1} = F_{\bullet}$より
$$ \lim_{n\to\infty} \frac{F_{n}}{F_{n+1}} = \lim_{n\to\infty} \frac{A_{n+1}}{B_{n+1}} = \lambda = \frac{-1+\sqrt{5}}{2}$$
となるので，逆数を取って
$$ \lim_{n\to\infty} \frac{F_{n+1}}{F_{n}} = \frac{1+\sqrt{5}}{2}$$
を得る．

整数列$q_{\bullet} \in \mathcal{Q}$と無理数$\lambda \in \mathbb{R}\smallsetminus\mathbb{Q}$とが対応しているとき，
$$ 0 \leq q_{0} \iff 0 < \lambda$$
が成り立つ．実際，

1. $0 \leq q_{0}$とすると，well-defの証明より，
   $$ 0 \leq q_{0} = \frac{A_{1}}{B_{1}} < \lambda$$
   が成り立つ．
2. $0 < \lambda$とすると，irr-euclidの証明より，
   $$ 0 \leq \lfloor \lambda \rfloor = q_{0}$$
   が成り立つ．

正整数$N \in \mathbb{Z}_{>0}$に対して，無理数$\lambda_{N} \in \mathbb{R}_{>0}\smallsetminus\mathbb{Q}$を
$$ \lambda_{N} \coloneqq [0;N,N,\ldots{}]$$
で定めると，
$$ \lambda_{N} = \frac{1}{N+\lambda_{N}} \quad\leadsto\quad \lambda_{N}^{2}+N\lambda_{N}-1 = 0$$
より，
$$ \lambda_{N} = \frac{-N+\sqrt{N^{2}+4}}{2}$$
となる．

ここで，
$$ \rho_{N} \coloneqq \lambda_{N}+N+1 = \frac{\sqrt{N^{2}+4}+N}{2} + 1,\ \sigma_{N} \coloneqq \lambda_{N}+1 = \frac{\sqrt{N^{2}+4}-N}{2}+1$$
とおくと，これらは
$$ \frac{1}{\rho_{N}}+\frac{1}{\sigma_{N}} = \frac{1}{\frac{1}{\lambda_{N}}+1}+\frac{1}{\lambda_{N}+1} = \frac{\lambda_{N}}{1+\lambda_{N}}+\frac{1}{\lambda_{N}+1} = 1$$
を満たす正の無理数であり，したがって
$$ \mathbb{N} = \{\lfloor \rho_{N}n \rfloor \mid n \in \mathbb{N}\} \sqcup \{\lfloor \sigma_{N}n \rfloor \mid n \in \mathbb{N}_{\geq 1}\}$$
が成り立つ（cf. Galois接続入門 例28，例29）．

上例より
$$ \frac{\sqrt{n^{2}+4}+n}{2} = [n;n,n,\ldots{}],\ \frac{\sqrt{n^{2}+4}-n}{2}+1 = [1;n,n,\ldots{}]$$
となるので，たとえば
$$ \frac{\sqrt{5}+1}{2} = [1;1,1,\ldots{}],\ \sqrt{2} = [1;2,2,\ldots{}] \notin \mathbb{Q}$$
が成り立つ．後者は
$$ \sqrt{n^{2}+1} = \frac{\sqrt{(2n)^{2}+4}-2n}{2} + n = [n;2n,2n,\ldots{}]$$
と一般化できる．

無理数$\lambda \in \mathbb{R}\smallsetminus\mathbb{Q}$の近似分数列$(A_{n}/B_{n})_{n=1}^{\infty}$について，
$$ \left| \lambda - \frac{A_{n+1}}{B_{n+1}} \right| < \left| \lambda - \frac{A_{n}}{B_{n}} \right| < \frac{1}{B_{n}^{2}q_{n}}$$
が成り立つ．

円周率$\pi = 3.1415926\cdots \in \mathbb{R}\smallsetminus\mathbb{Q}$について$q_{0},q_{1},q_{2},q_{3}$を計算すると，
\begin{align} 3.141592 &< \lambda_{0} = \pi < 3.1415927 &&\quad\leadsto\quad q_{0} = 3;\\ 7 + \frac{88511}{1415927} = \frac{1}{0.1415927} &< \lambda_{1} = \frac{1}{\lambda_{0}-3} < \frac{1}{0.141592} = 7 + \frac{1107}{17699} &&\quad\leadsto\quad q_{1} = 7;\\ 15 + \frac{1094}{1107} = \frac{17699}{1107} &< \lambda_{2} = \frac{1}{\lambda_{1}-7} < \frac{1415927}{88511} = 15 + \frac{88262}{88511} &&\quad\leadsto\quad q_{2} = 15;\\ 1 + \frac{249}{88262} = \frac{88511}{88262} &< \lambda_{3} = \frac{1}{\lambda_{2}-15} < \frac{1107}{1094} = 1 + \frac{13}{1094} &&\quad\leadsto\quad q_{3} = 1; \end{align}
となる．よって，$\pi$の近似分数として
\begin{align} \begin{bmatrix} 3 & 1 \\ 1 & 0 \end{bmatrix} &\quad\leadsto\quad \frac{A_{1}}{B_{1}} = \frac{3}{1} = 3;\\ \begin{bmatrix} 3 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 7 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 22 & 3 \\ 7 & 1 \end{bmatrix} &\quad\leadsto\quad \frac{A_{2}}{B_{2}} = \frac{22}{7} = 3 + \frac{1}{7} = 3.142857\cdots;\\ \begin{bmatrix} 22 & 3 \\ 7 & 1 \end{bmatrix}\begin{bmatrix} 15 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 333 & 22 \\ 106 & 7 \end{bmatrix} &\quad\leadsto\quad \frac{A_{3}}{B_{3}} = \frac{333}{106} = 3 + \frac{15}{106} = 3.141509\cdots;\\ \begin{bmatrix} 333 & 22 \\ 106 & 7 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 355 & 333 \\ 113 & 106 \end{bmatrix} &\quad\leadsto\quad \frac{A_{4}}{B_{4}} = \frac{355}{113} = 3 + \frac{16}{113} = 3.1415929\cdots; \end{align}
を得る．

公転周期$\varepsilon \in \mathbb{R}_{>0}\smallsetminus\mathbb{Q}$（日）の惑星で，$1$年を$c \coloneqq \lfloor \varepsilon \rfloor \in \mathbb{N}$（日）とする暦を用いているとする．このとき，季節と暦とのズレ$\lambda \coloneqq \varepsilon -c$の近似分数列$(A_{n}/B_{n})_{n=1}^{\infty}$について
$$ \frac{1}{2B_{n}B_{n+1}} < \left| \lambda - \frac{A_{n}}{B_{n}} \right| < \frac{1}{B_{n}^{2}}$$
が成り立つので，$B_{n}$年の間に閏年を$A_{n}$回設けることにすると，その間のズレは
$$ \frac{1}{2B_{n+1}} < \left| B_{n}\varepsilon - \left(B_{n}c + A_{n}\right)\right| < \frac{1}{B_{n}}$$
と評価できる（ただし，同じシステムを$2B_{n}B_{n+1}$年間使い続けるとズレが$1$を超えてしまう）．さて，たとえば
$$ 365.242188 < \varepsilon < 365.2422$$
の場合を考えると，
\begin{align} 0.242188 &< \lambda_{0} = \lambda = \varepsilon - 365 < 0.2422 &&\quad\leadsto\quad q_{0} = 0;\\ 4 + \frac{156}{1211} = \frac{1}{0.2422} &< \lambda_{1} = \frac{1}{\lambda_{0}-365} < \frac{1}{0.242188} = 4 + \frac{7812}{60547} &&\quad\leadsto\quad q_{1} = 4;\\ 7 + \frac{5863}{7812} = \frac{60547}{7812} &< \lambda_{2} = \frac{1}{\lambda_{1}-4} < \frac{1211}{156} = 7 + \frac{119}{156} &&\quad\leadsto\quad q_{2} = 7;\\ 1 + \frac{37}{119} = \frac{156}{119} &< \lambda_{3} = \frac{1}{\lambda_{2}-7} < \frac{7812}{5863} = 1 + \frac{1949}{5863} &&\quad\leadsto\quad q_{3} = 1;\\ 3 + \frac{16}{1949} = \frac{5863}{1949} &< \lambda_{4} = \frac{1}{\lambda_{3}-1} < \frac{119}{37} = 3 + \frac{8}{37} &&\quad\leadsto\quad q_{4} = 3;\\ \end{align}
より
\begin{align} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} &\quad\leadsto\quad \frac{A_{1}}{B_{1}} = \frac{0}{1} = 0;\\ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 4 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix} &\quad\leadsto\quad \frac{A_{2}}{B_{2}} = \frac{1}{4} = 0.25;\\ \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}\begin{bmatrix} 7 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 7 & 1 \\ 29 & 4 \end{bmatrix} &\quad\leadsto\quad \frac{A_{3}}{B_{3}} = \frac{7}{29} = 0.241379\cdots;\\ \begin{bmatrix} 7 & 1 \\ 29 & 4 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 8 & 7 \\ 33 & 29 \end{bmatrix} &\quad\leadsto\quad \frac{A_{4}}{B_{4}} = \frac{8}{33} = 0.242424\cdots;\\ \begin{bmatrix} 8 & 7 \\ 33 & 29 \end{bmatrix}\begin{bmatrix} 3 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 31 & 8 \\ 128 & 33 \end{bmatrix} &\quad\leadsto\quad \frac{A_{5}}{B_{5}} = \frac{31}{128} = 0.2421875; \end{align}
となる．ところで
$$ \lambda < \frac{8}{33} < \frac{97}{400} = 0.2425$$
であるから，$400$年間に$97$回の閏年を設けるよりも，$33$年間に$8$回の，或いは$128$年間に$31$回の閏年を設けるほうが，$1$年あたりのズレが小さい（cf. better-approx）：
$$ \left|\varepsilon - \left(365 + \frac{31}{128}\right)\right| < \left|\varepsilon - \left(365+\frac{8}{33}\right) \right| < \left|\varepsilon - \left(365 + \frac{97}{400}\right)\right|.$$