2
高校数学解説
文献あり

互除法から連分数へ

92
0
$$\newcommand{cl}[0]{\mathrm{Cl}} \newcommand{diam}[1]{\mathrm{diam}\left({#1}\right)} \newcommand{dist}[2]{\mathrm{dist}\left({#1},{#2}\right)} \newcommand{gen}[1]{\qty\langle#1\rangle} \newcommand{I}[0]{\mathrm{Int}} \newcommand{id}[0]{\mathrm{id}} \newcommand{incl}[2]{\mathrm{id}_{#1}^{#2}} \newcommand{Ker}[0]{\operatorname{Ker}} \newcommand{supp}[1]{\mathrm{supp}(#1)} \newcommand{transpose}[0]{\mathsf{T}} $$

Euclidの互除法

任意の$(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}$

  1. $d \mid a,\ d \mid b$;
  2. $d' \mid a,\ d' \mid b \implies d' \mid d$;

を満たすとき,$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)$とおく.

  1. $d \mid a,\ d \mid b$より
    $$ d \mid b,\ d \mid a-qb = r$$
    が成り立つ.
  2. $d' \mid b,\ d' \mid r$とすると,
    $$ d' \mid qb+r = a,\ d' \mid b$$
    となるので,$d' \mid d$を得る.

以上より,$d = \gcd(b,r)$が成り立つ.

Euclidの互除法

任意の$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}$$
を満たすものが存在する:

  1. $r_{0} \coloneqq a,\ r_{1} \coloneqq b$とおく.
  2. divisiongcdより自然数$r_{2} \in \mathbb{N}$であって
    $$ \gcd(r_{0},r_{1}) = \gcd(r_{1},r_{2}),\ 0 \leq r_{2} < r_{1}$$
    を満たすものがただ一つ存在する.
  3. $r_{2} \neq 0$のとき,同様にして$r_{3} \in \mathbb{N}$が定まる:
    $$ \gcd(r_{1},r_{2}) = \gcd(r_{2},r_{3}),\ 0 \leq r_{3} < r_{2}.$$
  4. 以下,これを繰り返せば,高々$b$回で$0$に達する.

したがって
$$ \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}$とする.このとき次は同値である:

  1. $\gcd(a,b) \mid c$;
  2. $\exists\, x,y \in \mathbb{Z},\ ax+by = c$.

とくに
$$ \gcd(a,b) = 1 \iff \exists\, x,y \in \mathbb{Z},\ ax+by=1$$
が成り立つ.

(i)$\implies$(ii)

仮定より$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$$
が成り立つ.

(ii)$\implies$(i)

明らか.

連分数

準備

実数列$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}$に関する数学的帰納法で示す.

  1. Base:
    $$ q_{0} = [q'_{0};q'_{1},\ldots,q'_{m-1}]$$
    とする.このとき,$m \geq 2$とすると
    $$ 0 < q_{0}-q'_{0} = \frac{1}{[q'_{1};q'_{2},\ldots,q'_{m-1}]} < 1$$
    となって$q_{0}-q'_{0} \in \mathbb{Z}$に反する.よって
    $$ m=1,\ q_{0} = q'_{0}$$
    が成り立つ.
  2. Induction:
    $$ [q_{0};q_{1},\ldots,q_{(n+1)-1}] = [q'_{0};q'_{1},\ldots,q'_{m-1}]$$
    とする.このとき,前段より$m \geq 2$であり,
    $$ q_{0} + \frac{1}{[q_{1};q_{2},\ldots,q_{n}]} = q'_{0} + \frac{1}{[q'_{1};q'_{2},\ldots,q'_{m-1}]}$$
    の整数部分を取って
    $$ q_{0}=q'_{0} \quad\leadsto\quad [q_{1};q_{2},\ldots,q_{n}] = [q'_{1};q'_{2},\ldots,q'_{m-1}]$$
    がわかるので,帰納法の仮定より
    $$ n = m-1,\ (q_{1},\ldots,q_{n}) = (q'_{1},\ldots,q'_{n})$$
    が成り立つ.

$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$$
が成り立つことに注意する.

  1. 有理数列$(A_{2n}/B_{2n})_{n=1}^{\infty}$について,
    \begin{align} \frac{A_{2n}}{B_{2n}} - \frac{A_{2n+2}}{B_{2n+2}} &= \frac{A_{2n}B_{2n+2} - A_{2n+2}B_{2n}}{B_{2n}B_{2n+2}} \\ &= \frac{A_{2n}(B_{2n+1}q_{2n+1}+B_{2n}) - (A_{2n+1}q_{2n+1}+A_{2n})B_{2n}}{B_{2n}B_{2n+2}} \\ &= -\frac{(A_{2n+1}B_{2n}-A_{2n}B_{2n+1})q_{2n+1}}{B_{2n}B_{2n+2}} \\ &= -\frac{(-1)^{2n+1}q_{2n+1}}{B_{2n}B_{2n+2}} \\ &= \frac{q_{2n+1}}{B_{2n}B_{2n+1}} \\ &> 0 \end{align}
    が成り立つ.
  2. 有理数列$(A_{2n-1}/B_{2n-1})_{n=1}^{\infty}$について,
    \begin{align} \frac{A_{2n-1}}{B_{2n-1}} - \frac{A_{2n+1}}{B_{2n+1}} &= \frac{A_{2n-1}B_{2n+1}-A_{2n+1}B_{2n-1}}{B_{2n-1}B_{2n+1}} \\ &= \frac{A_{2n-1}(B_{2n}q_{2n}+B_{2n-1}) - (A_{2n}q_{2n}+A_{2n-1})B_{2n-1}}{B_{2n-1}B_{2n+1}} \\ &= -\frac{(A_{2n}B_{2n-1}-A_{2n-1}B_{2n})q_{2n}}{B_{2n-1}B_{2n+1}} \\ &= -\frac{(-1)^{2n}q_{2n}}{B_{2n-1}B_{2n+1}} \\ &= -\frac{q_{2n}}{B_{2n-1}B_{2n+1}} \\ &< 0 \end{align}
    が成り立つ.
  3. 任意の$n \in \mathbb{Z}_{\geq 1}$に対して
    $$ A_{2n-1}B_{2n} - A_{2n}B_{2n-1} = -(-1)^{2n} = -1 < 0 \quad\leadsto\quad \frac{A_{2n-1}}{B_{2n-1}} < \frac{A_{2n}}{B_{2n}}$$
    が成り立つので,
    $$ \frac{A_{2n-1}}{B_{2n-1}} < \begin{dcases} \frac{A_{2n}}{B_{2n}} \leq \frac{A_{2m}}{B_{2m}} & n \geq m \\ \frac{A_{2m-1}}{B_{2m-1}} < \frac{A_{2m}}{B_{2m}} & n < m \end{dcases}$$
    を得る.よって,実数
    $$ \lim_{n\to\infty} \frac{A_{2n}}{B_{2n}},\ \lim_{n\to\infty} \frac{A_{2n-1}}{B_{2n-1}}$$
    が定まる.
  4. さらに,
    $$ \frac{A_{2n}}{B_{2n}} - \frac{A_{2n-1}}{B_{2n-1}} = \frac{(-1)^{2n}}{B_{2n}B_{2n-1}} = \frac{1}{B_{2n}B_{2n-1}} \to 0 \quad (n \to \infty)$$
    が成り立つので,
    $$ \lim_{n\to\infty} \frac{A_{2n}}{B_{2n}} = \lim_{n\to\infty} \frac{A_{2n-1}}{B_{2n-1}} \eqqcolon \lambda$$
    であり,したがって,有理数列$(A_{n}/B_{n})_{n=1}^{\infty}$$\lambda \in \mathbb{R}$に収束する.
  5. いま,任意の$n \in \mathbb{Z}_{\geq 1}$に対して
    $$ \frac{A_{2n-1}}{B_{2n-1}} < \lambda < \frac{A_{2n}}{B_{2n}} \quad\leadsto\quad 0 < \lambda - \frac{A_{2n-1}}{B_{2n-1}} < \frac{A_{2n}}{B_{2n}} - \frac{A_{2n-1}}{B_{2n-1}} = \frac{1}{B_{2n}B_{2n-1}}$$
    が成り立っている.したがって,$\lambda$が有理数であるとすると$(a,b) \in \mathbb{Z} \times \mathbb{Z}_{>0}$を用いて$\lambda = a/b$と表わせるので,十分大きな$n$に対して
    $$ 0 < aB_{2n-1} - A_{2n-1}b < \frac{b}{B_{2n}} < 1$$
    が成り立つことになり,$aB_{2n-1}-A_{2n-1}b \in \mathbb{Z}$に反する.

任意の$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}]$$
を満たすものが存在する.

  1. $\lambda_{0} \coloneqq \lambda,\ q_{0} \coloneqq \lfloor \lambda \rfloor$とおく.
  2. $q_{0} < \lambda_{0} < q_{0}+1$より
    $$ \lambda_{1} \coloneqq \frac{1}{\lambda_{0}-q_{0}} \in \mathbb{R}_{>1}\smallsetminus\mathbb{Q},\ q_{1} \coloneqq \lfloor \lambda_{1} \rfloor \in \mathbb{Z}_{>0}$$
    であり,
    $$ \lambda = \lambda_{0} = q_{0} + \frac{1}{\lambda_{1}} = [q_{0};\lambda_{1}]$$
    が成り立つ.
  3. $(\lambda_{0},\lambda_{1},\ldots,\lambda_{n}),\ (q_{0},q_{1},\ldots,q_{n})$まで定まったとする:
    $$ q_{k} = \lfloor \lambda_{k} \rfloor,\ \lambda = [q_{0};q_{1},\ldots,q_{n-1},\lambda_{n}].$$
    このとき,$q_{n} < \lambda_{n} < q_{n}+1$より
    $$ \lambda_{n+1} \coloneqq \frac{1}{\lambda_{n}-q_{n}} \in \mathbb{R}_{>1}\smallsetminus\mathbb{Q},\ q_{n+1} \coloneqq \lfloor \lambda_{n+1} \rfloor \in \mathbb{Z}_{>0}$$
    であり,
    $$ \lambda = [q_{0};q_{1},\ldots,q_{n-1},\lambda_{n}] = \left[q_{0};q_{1},\ldots,q_{n-1},q_{n}+\frac{1}{\lambda_{n+1}}\right] = [q_{0};q_{1},\ldots,q_{n-1},q_{n},\lambda_{n+1}]$$
    が成り立つ.

$\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-euclidlin-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-euclidapprox-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}$$
が成り立つことを示す.

  1. Base:定義より
    $$ \lambda'_{0} = \lambda' = [q_{0};q_{1},q_{2},\ldots{}]$$
    が成り立つ.また,
    $$ q_{0} < \lambda' < q_{0} + \frac{1}{q_{1}} \leq q_{0} + 1$$
    となるので,
    $$ q_{0} = \lfloor \lambda' \rfloor = q'_{0}$$
    が成り立つ.
  2. Induction:irr-euclidと帰納法の仮定より
    $$ \lambda' = [q'_{0};q'_{1},\ldots,q'_{n},\lambda'_{n+1}] = [q_{0};q_{1},\ldots,q_{n},\lambda'_{n+1}] = \begin{bmatrix} A_{n+1} & A_{n} \\ B_{n+1} & B_{n} \end{bmatrix} \star \lambda'_{n+1}$$
    となる.一方,
    $$ \lambda' = [q_{0};q_{1},\ldots,q_{n},[q_{n+1};q_{n+2},q_{n+3},\ldots{}]] = \begin{bmatrix} A_{n+1} & A_{n} \\ B_{n+1} & B_{n} \end{bmatrix} \star [q_{n+1};q_{n+2},q_{n+3},\ldots{}]$$
    であるから,
    $$ \lambda'_{n+1} = [q_{n+1};q_{n+2},q_{n+3},\ldots{}]$$
    を得る(cf. lin-frac-transf).したがって
    $$ q_{n+1} < \lambda'_{n+1} < q_{n+1}+\frac{1}{q_{n+2}} \leq q_{n+1} + 1$$
    となるので,
    $$ q_{n+1} = \lfloor \lambda'_{n+1} \rfloor = q'_{n+1}$$
    が成り立つ.

整数列$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}$に対して,既約分数
$$ \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|.$$

参考文献

[1]
岩堀長慶, 『2次行列の世界』, 岩波書店
[2]
木村俊一, 『連分数のふしぎ』, 講談社
[3]
高木貞治, 『初等整数論講義 第2版』, 共立出版
[4]
藤原松三郎, 『代数学 第一巻』, 内田老鶴圃
投稿日:614
更新日:614
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

うすい
74
15312
学んだことをまとめています.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中