任意の$(a,b) \in \mathbb{Z} \times \mathbb{Z}_{>0}$に対して,整数$q \in \mathbb{Z}$と自然数$r \in \mathbb{N}$であって
$$
a = qb + r,\ 0 \leq r < b$$
を満たすものがただ一組存在する.
$q \coloneqq \lfloor a/b \rfloor \in \mathbb{Z}$とおくと
$$
q \leq \frac{a}{b} < q + 1 \quad\leadsto\quad 0 \leq a - qb < b$$
が成り立つので,$r \coloneqq a-qb \in \mathbb{N}$とおけばよい.また,議論を逆に辿ることで一意性がわかる.
$a,b \in \mathbb{Z}$とする.自然数$d \in \mathbb{N}$が
を満たすとき,$d$を$a,b$の最大公約数といい,$\gcd(a,b)$で表わす.
任意の整数$a \in \mathbb{Z}$に対して
$$
\gcd(a,0) = |a|$$
が成り立つ.
$a,b,q,r \in \mathbb{Z}$をdivisionの通りとする.このとき
$$
\gcd(a,b) = \gcd(b,r)$$
が成り立つ.
$d \coloneqq \gcd(a,b)$とおく.
以上より,$d = \gcd(b,r)$が成り立つ.
任意の$a,b \in \mathbb{Z}$に対して,$x,y \in \mathbb{Z}$であって
$$
ax+by = \gcd(a,b)$$
を満たすものが存在する.
$b = 0$のとき
$$
a \cdot \mathrm{sign}(a) + b \cdot 1 = |a| = \gcd(a,b)$$
となるので,$b \neq 0$としてよい.また,
$$
ax+by = ax+(-b)(-y),\ \gcd(a,b) = \gcd(a,-b)$$
であるから,$b > 0$としてよい.このとき,整数の有限列$r_{0},r_{1},r_{2},\ldots,r_{n},r_{n+1}$であって
$$
\gcd(r_{0},r_{1}) = \gcd(r_{k},r_{k+1}),\ 0 = r_{n+1} < r_{n} < \cdots < r_{2} < r_{1}$$
を満たすものが存在する:
したがって
$$
\gcd(a,b) = \gcd(r_{0},r_{1}) = \gcd(r_{n},r_{n+1}) = \gcd(r_{n},0) = r_{n}$$
が成り立つ.ここで,各$k \in \{1,\ldots,n\}$に対して
$$
q_{k-1} \coloneqq \left\lfloor \frac{r_{k-1}}{r_{k}} \right\rfloor \in \mathbb{Z}$$
とおくと,
$$
r_{k-1} = q_{k-1}r_{k} + r_{k+1} \quad\leadsto\quad \begin{bmatrix}
r_{k-1} \\ r_{k}
\end{bmatrix} = \begin{bmatrix}
q_{k-1} & 1 \\ 1 & 0
\end{bmatrix} \begin{bmatrix}
r_{k} \\ r_{k+1}
\end{bmatrix}$$
であるから,
$$
\begin{bmatrix}
a \\ b
\end{bmatrix} =
\begin{bmatrix}
q_{0} & 1 \\ 1 & 0
\end{bmatrix}
\begin{bmatrix}
q_{1} & 1 \\ 1 & 0
\end{bmatrix} \cdots
\begin{bmatrix}
q_{n-1} & 1 \\ 1 & 0
\end{bmatrix}
\begin{bmatrix}
r_{n} \\ 0
\end{bmatrix}$$
が成り立つ.よって,等式
$$
\begin{bmatrix}
0 & 1 \\ 1 & -q_{n-1}
\end{bmatrix} \cdots
\begin{bmatrix}
0 & 1 \\ 1 & -q_{1}
\end{bmatrix}
\begin{bmatrix}
0 & 1 \\ 1 & -q_{0}
\end{bmatrix}
\begin{bmatrix}
a \\ b
\end{bmatrix} =
\begin{bmatrix}
r_{n} \\ 0
\end{bmatrix} = \begin{bmatrix}
\gcd(a,b) \\ 0
\end{bmatrix}$$
において両辺の$(1,1)$成分を比較することで結論を得る.
$0 < r_{n} < \cdots < r_{1}$より,各$k \in \{1,\ldots,n-1\}$に対して
$$
1 < \frac{r_{k}}{r_{k+1}} \quad\leadsto\quad 1 \leq \left\lfloor \frac{r_{k}}{r_{k+1}} \right\rfloor = q_{k}$$
が成り立つ.
$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$$
を得る.
$a,b,c \in \mathbb{Z}$とする.このとき次は同値である:
とくに
$$
\gcd(a,b) = 1 \iff \exists\, x,y \in \mathbb{Z},\ ax+by=1$$
が成り立つ.
仮定より$c' \in \mathbb{Z}$であって$\gcd(a,b)c' = c$なるものが存在する.また,euclidより$x_{0},y_{0} \in \mathbb{Z}$であって
$$
ax_{0}+by_{0} = \gcd(a,b)$$
を満たすものが存在する.よって
$$
a \cdot x_{0}c' + b \cdot y_{0}c' = \gcd(a,b)c' = c$$
が成り立つ.
明らか.
実数列$q_{\bullet} \in \mathbb{R}^{\mathbb{N}}$であって
$$
\forall n \geq 1,\ q_{n} > 0$$
なるものに対して,実数列$A_{\bullet},B_{\bullet}$を,$(A_{0},B_{0}) \coloneqq (1,0)$および
$$
\begin{bmatrix}
A_{n} \\ B_{n}
\end{bmatrix} \coloneqq
\begin{bmatrix}
q_{0} & 1 \\ 1 & 0
\end{bmatrix}
\begin{bmatrix}
q_{1} & 1 \\ 1 & 0
\end{bmatrix} \cdots
\begin{bmatrix}
q_{n-1} & 1 \\ 1 & 0
\end{bmatrix} \begin{bmatrix}
1 \\ 0
\end{bmatrix},\ n \geq 1$$
で定める.このとき,
$$
\begin{bmatrix}
q_{n-2} & 1 \\ 1 & 0
\end{bmatrix} \begin{bmatrix}
1 \\ 0
\end{bmatrix} =
\begin{bmatrix}
q_{n-2} & 1 \\ 1 & 0
\end{bmatrix}\begin{bmatrix}
q_{n-1} & 1 \\ 1 & 0
\end{bmatrix} \begin{bmatrix}
0 \\ 1
\end{bmatrix},\ n \geq 2$$
より,
$$
\begin{bmatrix}
A_{n} & A_{n-1} \\ B_{n} & B_{n-1}
\end{bmatrix} =
\begin{bmatrix}
q_{0} & 1 \\ 1 & 0
\end{bmatrix}
\begin{bmatrix}
q_{1} & 1 \\ 1 & 0
\end{bmatrix} \cdots
\begin{bmatrix}
q_{n-1} & 1 \\ 1 & 0
\end{bmatrix},\ n \geq 1$$
が成り立つ.
任意の$n \in \mathbb{Z}_{\geq 1}$に対して$B_{n} > 0$が成り立つ.また,$q_{\bullet}$が整数列ならば,任意の$n \in \mathbb{Z}_{\geq 2}$に対して
$$
0 < n-1 \leq B_{n} < B_{n+1}$$
が成り立つ.
明らかに
$$
0 < 1 = B_{1}$$
であり,漸化式
$$
\begin{bmatrix}
A_{n+1} & A_{n} \\ B_{n+1} & B_{n}
\end{bmatrix} =
\begin{bmatrix}
A_{n} & A_{n-1} \\ B_{n} & B_{n-1}
\end{bmatrix} \begin{bmatrix}
q_{n} & 1 \\ 1 & 0
\end{bmatrix} =
\begin{bmatrix}
A_{n}q_{n} + A_{n-1} & A_{n} \\
B_{n}q_{n} + B_{n-1} & B_{n}
\end{bmatrix}$$
より,
$$
0 < B_{1},\ldots,B_{n} \implies 0 < B_{n}q_{n} \leq B_{n}q_{n} + B_{n-1} = B_{n+1}$$
が成り立つ.また,$q_{\bullet}$が整数列のとき,
$$
0 < 1 = B_{1} \leq B_{1}q_{1} = B_{1}q_{1}+B_{0} = B_{2} \leq B_{2}q_{2} < B_{2}q_{2}+B_{1} = B_{3}$$
および
$$
n-1 \leq B_{n} < B_{n+1} \implies n \leq B_{n+1} \leq B_{n+1}q_{n+1} < B_{n+1}q_{n+1}+B_{n} = B_{n+2}$$
が成り立つ.
分数$\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}
となる.
上述の記号のもとで,任意の$n \in \mathbb{Z}_{\geq 1}$に対して
$$
\frac{A_{n}}{B_{n}} = q_{0} + \cfrac{1}{q_{1}+\cfrac{1}{q_{2}+\cfrac{1}{q_{3}+\cfrac{1}{\ddots + \cfrac{1}{q_{n-1}}}}}} \eqqcolon [q_{0};q_{1},\ldots,q_{n-1}]$$
が成り立つ.
“長さ”$n$に関する数学的帰納法に拠る.$n=1,2$のときは上例より明らかであり,$n \geq 2$のとき,
$$
\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} + \frac{1}{q_{n}} & 1 \\ 1 & 0
\end{bmatrix} \begin{bmatrix}
1 \\ 0
\end{bmatrix} = \begin{bmatrix}
A_{n-1} & A_{n-2} \\ B_{n-1} & B_{n-2}
\end{bmatrix}\begin{bmatrix}
q_{n-1} + \frac{1}{q_{n}} \\ 1
\end{bmatrix} = \begin{bmatrix}
A_{n-1}(q_{n-1}+\frac{1}{q_{n}}) + A_{n-2} \\ B_{n-1}(q_{n-1}+\frac{1}{q_{n}}) + B_{n-2}
\end{bmatrix}$$
より,
\begin{align}
[q_{0};q_{1},\ldots,q_{(n+1)-1}]
&= [q_{0};q_{1},\ldots,q_{n-2},q_{n-1}+\tfrac{1}{q_{n}}] \\
&= \frac{A_{n-1}(q_{n-1}+\frac{1}{q_{n}})+A_{n-2}}{B_{n-1}(q_{n-1}+\frac{1}{q_{n}})+B_{n-2}} \\
&= \frac{A_{n-1}(q_{n-1}q_{n}+1)+A_{n-2}q_{n}}{B_{n-1}(q_{n-1}q_{n}+1)+B_{n-2}q_{n}} \\
&= \frac{(A_{n-1}q_{n-1}+A_{n-2})q_{n}+A_{n-1}}{(B_{n-1}q_{n-1}+B_{n-2})q_{n}+B_{n-1}} \\
&= \frac{A_{n}q_{n}+A_{n-1}}{B_{n}q_{n}+B_{n-1}} \\
&= \frac{A_{n+1}}{B_{n+1}}
\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}
と書ける.
有理数$\lambda = a/b \in \mathbb{Q},\ (a,b) \in \mathbb{Z} \times \mathbb{Z}_{>0},\ \gcd(a,b)=1,$に対して,euclidの証明より
$$
\begin{bmatrix}
a \\ b
\end{bmatrix} =
\begin{bmatrix}
q_{0} & 1 \\ 1 & 0
\end{bmatrix}
\begin{bmatrix}
q_{1} & 1 \\ 1 & 0
\end{bmatrix} \cdots
\begin{bmatrix}
q_{n-1} & 1 \\ 1 & 0
\end{bmatrix} \begin{bmatrix}
1 \\ 0
\end{bmatrix}$$
であるから,
$$
\lambda = \frac{a}{b} = [q_{0};q_{1},\ldots,q_{n-1}] = q_{0} + \cfrac{1}{q_{1}+\cfrac{1}{q_{2}+\cfrac{1}{q_{3}+\cfrac{1}{\ddots + \cfrac{1}{q_{n-1}}}}}}$$
となる(cf. quoti-posi).これを$\lambda$の(正則)連分数展開という.
写像
$$
f \colon \bigcup_{n=1}^{\infty} \{(q_{0},q_{1},\ldots,q_{n-1}) \mid q_{0} \in \mathbb{Z},\ q_{1},\ldots,q_{n-1} \in \mathbb{Z}_{>0},\ q_{n-1} > 1\} \to \mathbb{Q};\ (q_{0},q_{1},\ldots,q_{n-1}) \mapsto [q_{0};q_{1},\ldots,q_{n-1}]$$
は全単射である.
任意の$n \in \mathbb{Z}_{\geq 2}$に対して,$q_{n-1}>1$より,
$$
[q_{1};q_{2},\ldots,q_{n-1}] > 1$$
が成り立つ.実際,$n=2$のときは明らかであり,$n$のとき成り立てば$n+1$でも成り立つ:
$$
[q_{1};q_{2},\ldots,q_{(n+1)-1}] = [q_{1};[q_{2};q_{3},\ldots,q_{n}]] = q_{1} + \frac{1}{[q_{2};q_{3},\ldots,q_{n}]} > q_{1} \geq 1.$$
euclidの証明において
$$
q_{n-1}r_{n} = r_{n-1} > r_{n} > 0 \quad\leadsto\quad q_{n-1} > 1$$
が成り立つので,写像$f$は全射である.したがって,あとは単射性を示せばよい.そこで$f(q_{\bullet}) = f(q'_{\bullet})$とする.このとき$q_{\bullet} = q'_{\bullet}$となることを,$q_{\bullet}$の“長さ”$n \in \mathbb{Z}_{\geq 1}$に関する数学的帰納法で示す.
$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).
$\mathbb{R}^{\mathbb{N}}$の部分集合$\mathcal{Q}$を
$$
\mathcal{Q} \coloneqq \{q_{\bullet} = (q_{0},q_{1},q_{2},\ldots{}) \in \mathbb{Z}^{\mathbb{N}} \mid \forall n \geq 1,\ q_{n} > 0\}$$
で定める.以下,$\mathcal{Q}$と$\mathbb{R}\smallsetminus\mathbb{Q}$との間に全単射が存在することを示す.
整数列$q_{\bullet} \in \mathcal{Q}$に対して,整数列$A_{\bullet},B_{\bullet}$を
$$
\begin{bmatrix}
A_{n} & A_{n-1} \\ B_{n} & B_{n-1}
\end{bmatrix} \coloneqq
\begin{bmatrix}
q_{0} & 1 \\ 1 & 0
\end{bmatrix}
\begin{bmatrix}
q_{1} & 1 \\ 1 & 0
\end{bmatrix} \cdots
\begin{bmatrix}
q_{n-1} & 1 \\ 1 & 0
\end{bmatrix}$$
で定めると,$\gcd(A_{n},B_{n}) = 1$であり,有理数列$(A_{n}/B_{n})_{n=1}^{\infty}$はある無理数に収束する:
$$
[q_{0};q_{1},q_{2},\ldots{}] \coloneqq \lim_{n\to\infty} \frac{A_{n}}{B_{n}} \in \mathbb{R}\smallsetminus\mathbb{Q}.$$
定義式において両辺のディターミナントを取ると
$$
A_{n}B_{n-1}-A_{n-1}B_{n} = (-1)^{n}$$
となるので,coprimeより,$\gcd(A_{n},B_{n}) = 1$を得る.また,Bn-posiより
$$
\lim_{n\to\infty} B_{n} = \infty$$
が成り立つことに注意する.
任意の$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}$$
を得る.
$\lambda \in \mathbb{R}\smallsetminus\mathbb{Q}$とする.このとき,無理数列$\lambda_{\bullet} \in \mathbb{R}^{\mathbb{N}}$と整数列$q_{\bullet} \in \mathcal{Q}$とであって
$$
\forall n \in \mathbb{Z}_{\geq 1},\ \lambda_{n} > 1,\ \lambda = [q_{0};q_{1},\ldots,q_{n-1},\lambda_{n}]$$
を満たすものが存在する.
$\lambda$が有理数$r_{0}/r_{1}$のとき,上の手続きはEuclidの互除法に外ならない:
\begin{align}
r_{0} &= q_{0}r_{1} + r_{2},\ q_{0} = \left\lfloor \frac{r_{0}}{r_{1}} \right\rfloor,\ 0 < r_{2} < r_{1} &&\leadsto\quad q_{0} + \frac{r_{2}}{r_{1}} = \frac{r_{0}}{r_{1}} = \lambda \eqqcolon \lambda_{0},\ q_{0} = \lfloor \lambda_{0} \rfloor;\\
r_{1} &= q_{1}r_{2} + r_{3},\ q_{1} = \left\lfloor \frac{r_{1}}{r_{2}} \right\rfloor,\ 0 < r_{3} < r_{2} &&\leadsto\quad q_{1} + \frac{r_{3}}{r_{2}} = \frac{r_{1}}{r_{2}} = \frac{1}{\lambda_{0}-q_{0}} \eqqcolon \lambda_{1} > 1,\ q_{1} = \lfloor \lambda_{1} \rfloor;\\
r_{2} &= q_{2}r_{3} + r_{4},\ q_{2} = \left\lfloor \frac{r_{2}}{r_{3}} \right\rfloor,\ 0 < r_{4} < r_{3} &&\leadsto\quad q_{2} + \frac{r_{4}}{r_{3}} = \frac{r_{2}}{r_{3}} = \frac{1}{\lambda_{1}-q_{1}} \eqqcolon \lambda_{2} > 1,\ q_{2} = \lfloor \lambda_{2} \rfloor;\\
&\quad\vdots &&\ \ \vdots \\
r_{n-1} &= q_{n-1}r_{n}+r_{n+1},\ 0 = r_{n+1} < r_{n} &&\leadsto\quad q_{n-1} = \frac{r_{n-1}}{r_{n}} = \frac{1}{\lambda_{n-2}-q_{n-2}} \eqqcolon \lambda_{n-1} > 1.\\
\end{align}
無理数$\lambda \in \mathbb{R}\smallsetminus\mathbb{Q}$から定まる整数列$q_{\bullet} \in \mathcal{Q}$(から定まる整数列$A_{\bullet},B_{\bullet}$)に対して,
$$
\lim_{n\to\infty} \frac{A_{n}}{B_{n}} = \lambda$$
が成り立つ.
irr-euclid,lin-frac-transfより,任意の$n \in \mathbb{Z}_{\geq 1}$に対して
$$
\lambda = [q_{0};q_{1},\ldots,q_{n-1},\lambda_{n}] = \begin{bmatrix}
A_{n} & A_{n-1} \\ B_{n} & B_{n-1}
\end{bmatrix} \star \lambda_{n} = \frac{A_{n}\lambda_{n}+A_{n-1}}{B_{n}\lambda_{n}+B_{n-1}}$$
が成り立つ.よって
$$
\frac{A_{n}}{B_{n}} - \lambda = \frac{A_{n}}{B_{n}} - \frac{A_{n}\lambda_{n}+A_{n-1}}{B_{n}\lambda_{n}+B_{n-1}} = \frac{(-1)^{n}}{B_{n}(B_{n}\lambda_{n}+B_{n-1})}$$
と合わせて,
$$
\left| \frac{A_{n}}{B_{n}} - \lambda \right| = \frac{1}{B_{n}(B_{n}\lambda_{n}+B_{n-1})} < \frac{1}{B_{n}(B_{n}q_{n}+B_{n-1})} = \frac{1}{B_{n}B_{n+1}} \to \infty \quad (n \to \infty)$$
を得る(cf. Bn-posi).
無理数$\lambda \in \mathbb{R}\smallsetminus\mathbb{Q}$に対して,
$$
\lambda = \lim_{n\to\infty} \frac{A_{n}}{B_{n}} = [q_{0};q_{1},q_{2},\ldots{}]$$
を$\lambda$の(正則)連分数展開という.
写像
$$
\mathcal{Q} \to \mathbb{R}\smallsetminus\mathbb{Q};\ q_{\bullet} \mapsto [q_{0};q_{1},q_{2},\ldots{}]$$
は全単射である.
irr-euclid,approx-fracより
$$
\lambda \mapsto q_{\bullet} \mapsto [q_{0};q_{1},q_{2},\ldots{}] = \lambda$$
が成り立つ.そこで,$q_{\bullet} \in \mathcal{Q}$とし
$$
\lambda' \coloneqq [q_{0};q_{1},q_{2},\ldots{}] \in \mathbb{R}\smallsetminus\mathbb{Q}$$
とおく.また,無理数$\lambda'$から定まる無理数列および整数列をそれぞれ$\lambda'_{\bullet},\,q'_{\bullet}$とする(cf. irr-euclid).このとき,任意の$n \in \mathbb{N}$に対して
$$
\lambda'_{n} = [q_{n};q_{n+1},q_{n+2},\ldots{}],\ q_{n} = q'_{n}$$
が成り立つことを示す.
整数列$q_{\bullet} \in \mathcal{Q}$と無理数$\lambda \in \mathbb{R}\smallsetminus\mathbb{Q}$とが対応しているとき,
$$
0 \leq q_{0} \iff 0 < \lambda$$
が成り立つ.実際,
正整数$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}$に対して,既約分数
$$
\frac{A_{k}}{B_{k}} = [q_{0};q_{1},\ldots,q_{k-1}] \in \mathbb{Q},\ k \geq 1$$
を$\lambda$の(主)近似分数という.
無理数$\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}}$$
が成り立つ.
approx-fracの証明より
$$
\left| \lambda - \frac{A_{n}}{B_{n}} \right| < \frac{1}{B_{n}B_{n+1}} \leq \frac{1}{B_{n}^{2}q_{n}}$$
および
$$
\lambda-\frac{A_{k}}{B_{k}} = \frac{(-1)^{k+1}}{B_{k}(B_{k}\lambda_{k}+B_{k-1})}$$
が成り立つ.後者より,$\lambda$は$A_{n+1}/B_{n+1},A_{n}/B_{n}$を端点とする(開)区間に属していることがわかる.さらに,
$$
B_{n+2} = B_{n+1}q_{n+1}+B_{n} \geq B_{n+1} + B_{n} \geq 2B_{n}$$
より
$$
\left|\lambda-\frac{A_{n+1}}{B_{n+1}}\right| < \frac{1}{B_{n+1}B_{n+2}} \leq \frac{1}{2}\frac{1}{B_{n}B_{n+1}}$$
となるので,
$$
\left|\lambda-\frac{A_{n+1}}{B_{n+1}}\right| + \left|\lambda-\frac{A_{n}}{B_{n}}\right| = \left| \frac{A_{n+1}}{B_{n+1}} - \frac{A_{n}}{B_{n}} \right| = \frac{1}{B_{n}B_{n+1}}$$
と合わせて
$$
\left|\lambda-\frac{A_{n+1}}{B_{n+1}}\right| < \frac{1}{2}\frac{1}{B_{n}B_{n+1}} < \left|\lambda-\frac{A_{n}}{B_{n}}\right|$$
を得る.
有理数の場合も同様の不等式が成り立つ.
円周率$\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|.$$