連分数（高校数学）

同義語：continued fractions (high school mathematics)

概要

前提知識: 整数の割り算と互除法, 実数とは何か：無理数の証明, Fibonacci数の整数の性質

高校での出発点：互除法の商を並べる

互除法で最大公約数を求めるとき、割り算の商は使わずに捨ててしまうことが多い。この記事では、捨てていた商を並べると何が分かるかを調べる。

$\dfrac{157}{68}$ を分数の入れ子にする

$157$ と $68$ に互除法を使う。
$$ 157=2\cdot68+21,\qquad 68=3\cdot21+5,\qquad 21=4\cdot5+1,\qquad 5=5\cdot1 $$
各段の等式の両辺を割る数で割ると
$$ \frac{157}{68}=2+\frac{21}{68}=2+\cfrac{1}{\frac{68}{21}},\qquad \frac{68}{21}=3+\frac5{21}=3+\cfrac1{\frac{21}5},\qquad \frac{21}5=4+\frac15 $$
である。下の式を上の式に順に代入すると
$$ \frac{157}{68}=2+\cfrac{1}{3+\cfrac{1}{4+\cfrac{1}{5}}} $$
となる。分数の入れ子に現れる $2,3,4,5$ は、互除法の商そのものである。

図 1 は、この計算を長方形で見たものである。$157\times68$ の長方形から、1 辺 $68$ の正方形を取れるだけ取ると $2$ 個取れて、$21\times68$ の長方形が残る。そこから 1 辺 $21$ の正方形を $3$ 個取ると $21\times5$ が残り、1 辺 $5$ の正方形を $4$ 個、最後に 1 辺 $1$ の正方形を $5$ 個取ると、ちょうど埋まる。取った正方形の個数 $2,3,4,5$ が互除法の商である。
157 × 68 の長方形を、取れるだけ大きな正方形で順に埋めた図。正方形の個数は 2、3、4、5 で、右は赤枠の部分の拡大
無理数でも同じことができる。

$\sqrt2$ を分数の入れ子にする

$1<\sqrt2<2$ なので、$\sqrt2=1+(\sqrt2-1)$ と整数の部分と $0$ と $1$ の間の部分に分ける。$0$ と $1$ の間の部分の逆数は、分母を有理化して
$$ \frac1{\sqrt2-1}=\frac{\sqrt2+1}{(\sqrt2-1)(\sqrt2+1)}=\sqrt2+1=2+(\sqrt2-1) $$
である。同じ $\sqrt2-1$ がまた現れたので、同じ計算が限りなく続く：
$$ \sqrt2=1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}} $$
途中で打ち切ると
$$ 1,\qquad 1+\frac12=\frac32,\qquad 1+\cfrac1{2+\cfrac12}=\frac75,\qquad 1+\cfrac1{2+\cfrac1{2+\cfrac12}}=\frac{17}{12},\ \ldots $$
で、$\sqrt2=1.41421\ldots$ に対し $1.5$、$1.4$、$1.41666\ldots$ と近づいていく。

この記事で答える問いは次の 4 つである。

どの有理数も、このような有限の入れ子で書けるか。書き方は 1 通りか。→ prop-cfh-rational、rem-cfh-unique
入れ子を打ち切った分数を、内側から計算し直さずに求める方法はあるか。→ thm-cfh-recurrence
打ち切った分数は、もとの数にどれくらい近いか。→ thm-cfh-approx

小数を打ち切るのと比べて、何がよいか。→ ex-cfh-cx-decimal

高校の計算	この記事の言葉	大学の言葉
互除法の商	連分数の成分 $a_k$	Euclid の互除法の商の列
途中で打ち切った分数	近似分数 $\dfrac{p_k}{q_k}$	有理数による近似
拡張互除法（Bézout の等式）	$p_kq_{k-1}-p_{k-1}q_k=\pm1$	行列式 $\pm1$ の整数行列
分母の有理化で同じ数が現れる	連分数が循環する	2 次の無理数（Lagrange の定理）

連分数の定義

連分数

実数 $a_0$ と正の実数 $a_1,\ldots,a_n$ に対し
$$ [a_0;a_1,a_2,\ldots,a_n]=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{\ddots+\cfrac{1}{a_n}}}} $$
と書き、これを 連分数 という。正確には、$[a_0]=a_0$ とし、$n\ge1$ では
$$ [a_0;a_1,\ldots,a_n]=a_0+\frac1{[a_1;a_2,\ldots,a_n]} $$
と内側から順に定める。$a_0,a_1,\ldots,a_n$ を連分数の成分という。$a_0$ が整数で $a_1,\ldots,a_n$ が正の整数のとき、有限の単純連分数 という。

$a_1,\ldots,a_n$ が正なので、$[a_1;a_2,\ldots,a_n]\ge a_1>0$ であり（成分の個数についての帰納法）、定義の中で $0$ で割ることはない。定義の式を最後の 2 つの成分に使うと
$$ [a_0;a_1,\ldots,a_{n-1},a_n]=\Bigl[a_0;a_1,\ldots,a_{n-2},\ a_{n-1}+\frac1{a_n}\Bigr] $$
が成り立つ（右辺の最後の成分は整数とは限らない正の実数である）。$n=1$ では両辺とも $a_0+\frac1{a_1}$ であり、$n\ge2$ では両辺を $a_0+\frac1{[\,\cdots]}$ と展開すると、内側の連分数について成分が 1 個少ない同じ式になるので、成分の個数についての帰納法で示せる。これを後の証明で使う。

連分数の値を計算する

$[1;2,2]$：内側から $2+\dfrac12=\dfrac52$、$1+\dfrac25=\dfrac75$ なので $[1;2,2]=\dfrac75$ である。
$[2;3,4,5]$：内側から $4+\dfrac15=\dfrac{21}5$、$3+\dfrac5{21}=\dfrac{68}{21}$、$2+\dfrac{21}{68}=\dfrac{157}{68}$ なので $[2;3,4,5]=\dfrac{157}{68}$ である。ex-cfh-start と合っている。

有理数は有限の連分数で書ける

有理数の連分数展開

整数 $a$ と正の整数 $b$ に対し、$\dfrac ab$ は有限の単純連分数 $[a_0;a_1,\ldots,a_n]$ で表せる。$a_0,a_1,\ldots,a_n$ は $a$ と $b$ に互除法を行ったときの商であり、$n\ge1$ なら最後の成分は $a_n\ge2$ である。

段 1（互除法を書く）。$s_0=a$、$s_1=b$ とし、整数の割り算と互除法の割り算の定理で
$$ s_i=a_is_{i+1}+s_{i+2},\qquad 0\le s_{i+2}< s_{i+1}\qquad(i=0,1,2,\ldots) $$
と割っていき、$s_{n+2}=0$ となったところで止める（余りは真に減るので必ず止まる）。
段 2（成分の符号）。$i\ge1$ では $s_i>s_{i+1}>0$ なので、商 $a_i$ は $1$ 以上の整数である。$n\ge1$ なら、最後の段は $s_n=a_ns_{n+1}$ で、$s_n>s_{n+1}$ から $a_n\ge2$ である。
段 3（連分数になる）。$i=n,n-1,\ldots,0$ の順に、$\dfrac{s_i}{s_{i+1}}=[a_i;a_{i+1},\ldots,a_n]$ を示す。$i=n$ では $\dfrac{s_n}{s_{n+1}}=a_n=[a_n]$ である。$i< n$ では $s_{i+2}>0$ なので
$$ \frac{s_i}{s_{i+1}}=a_i+\frac{s_{i+2}}{s_{i+1}}=a_i+\cfrac1{\frac{s_{i+1}}{s_{i+2}}}=a_i+\frac1{[a_{i+1};\ldots,a_n]}=[a_i;a_{i+1},\ldots,a_n] $$
である（3 つ目の等号で $i+1$ の場合を使った）。$i=0$ の場合が $\dfrac ab=[a_0;a_1,\ldots,a_n]$ である。$\square$

有理数を展開する

$\dfrac{43}{30}$：$43=1\cdot30+13$、$30=2\cdot13+4$、$13=3\cdot4+1$、$4=4\cdot1$ なので $\dfrac{43}{30}=[1;2,3,4]$ である。
$\dfrac{1071}{462}$：整数の割り算と互除法の最初の例の商は $2,3,7$ で、$\dfrac{1071}{462}=[2;3,7]$ である。
負の数 $-\dfrac{7}{5}$：$-7=(-2)\cdot5+3$、$5=1\cdot3+2$、$3=1\cdot2+1$、$2=2\cdot1$ なので $-\dfrac75=[-2;1,1,2]$ である。$a_0$ だけは負になりうる。

表し方の一意性

最後の成分を $1$ にしてよいなら、$a_n\ge2$ のとき $[a_0;\ldots,a_{n-1},a_n]=[a_0;\ldots,a_{n-1},a_n-1,1]$ と書き直せる（$a_n-1+\frac11=a_n$）。そこで「$n\ge1$ なら最後の成分は $2$ 以上」と約束すると、有理数を有限の単純連分数で表す方法はただ 1 通りになる。

ただ 1 通りであることの証明を開く

$x=[a_0;a_1,\ldots,a_n]$（約束を満たす単純連分数）とする。$n=0$ なら $x=a_0$ は整数である。$n\ge1$ なら $y=[a_1;\ldots,a_n]$ は $1$ より大きい：$n=1$ なら $y=a_1\ge2$、$n\ge2$ なら $y=a_1+\frac1{[a_2;\ldots,a_n]}$ で $[a_2;\ldots,a_n]>0$ から $y>a_1\ge1$ である。よって $x=a_0+\frac1y$ で $0<\frac1y<1$ なので、$x$ は整数でなく、$a_0$ は $x$ 以下の最大の整数 $\lfloor x\rfloor$ である。

そこで 2 通りの表し方 $[a_0;a_1,\ldots,a_n]=[b_0;b_1,\ldots,b_m]$ があるとする。$x$ が整数なら上のことから $n=m=0$、$a_0=b_0=x$ である。$x$ が整数でないなら $n,m\ge1$ で、$a_0=b_0=\lfloor x\rfloor$ となり、$\frac1{x-a_0}=[a_1;\ldots,a_n]=[b_1;\ldots,b_m]$ である。成分の個数についての帰納法により、残りの成分も一致する。

主定理 1：近似分数の漸化式

ex-cfh-start-sqrt2 では、打ち切った分数を毎回内側から計算し直した。実は、打ち切った分数の分子と分母は、漸化式で順に求められる。

近似分数

実数 $a_0$ と正の実数 $a_1,a_2,\ldots$（有限個でも無限個でもよい）に対し、
$$ p_{-2}=0,\quad p_{-1}=1,\qquad q_{-2}=1,\quad q_{-1}=0 $$
から始めて、$k=0,1,2,\ldots$ について
$$ p_k=a_kp_{k-1}+p_{k-2},\qquad q_k=a_kq_{k-1}+q_{k-2} $$
と定める。$\dfrac{p_k}{q_k}$ を 第 $k$ 近似分数 という。

最初のいくつかを書くと、$p_0=a_0$、$q_0=1$、$p_1=a_1a_0+1$、$q_1=a_1$ である。$\dfrac{p_0}{q_0}=a_0=[a_0]$、$\dfrac{p_1}{q_1}=a_0+\dfrac1{a_1}=[a_0;a_1]$ となっている。

$[2;3,4,5]$ の近似分数を表で求める

$p_k$ の行は「上の成分 $a_k$ × 左の数＋ 2 つ左の数」で埋める。$q_k$ の行も同じである。

$k$	$-2$	$-1$	$0$	$1$	$2$	$3$
$a_k$			$2$	$3$	$4$	$5$
$p_k$	$0$	$1$	$2$	$7$	$30$	$157$
$q_k$	$1$	$0$	$1$	$3$	$13$	$68$
$p_kq_{k-1}-p_{k-1}q_k$		$1$	$-1$	$1$	$-1$	$1$

たとえば $p_2=4\cdot7+2=30$、$q_2=4\cdot3+1=13$、$p_3=5\cdot30+7=157$、$q_3=5\cdot13+3=68$ である。最後の $\dfrac{p_3}{q_3}=\dfrac{157}{68}$ はもとの分数で、途中の $\dfrac{p_2}{q_2}=\dfrac{30}{13}$ は $[2;3,4]=2+\cfrac1{3+\cfrac14}=2+\dfrac4{13}=\dfrac{30}{13}$ と一致する。最後の行は $\pm1$ が交互に並ぶ。

近似分数の漸化式

実数 $a_0$ と正の実数 $a_1,\ldots,a_n$ について、def-cfh-convergent の $p_k,q_k$ は次を満たす。
(1) $0\le k\le n$ で $q_k>0$ であり、$[a_0;a_1,\ldots,a_k]=\dfrac{p_k}{q_k}$ である。
(2) $-1\le k\le n$ で $p_kq_{k-1}-p_{k-1}q_k=(-1)^{k-1}$ である。
(3) $a_0$ が整数で $a_1,\ldots,a_n$ が正の整数なら、$p_k,q_k$ は整数で、$\dfrac{p_k}{q_k}$ は既約分数である。

の $q_k>0$。$q_0=1>0$、$q_1=a_1>0$ である。$k\ge2$ で $q_{k-1}>0$、$q_{k-2}>0$ なら $q_k=a_kq_{k-1}+q_{k-2}>0$ である。
の等式。「成分が $k+1$ 個（$a_0$ から $a_k$ まで）のどんな連分数でも $[a_0;\ldots,a_k]=\dfrac{p_k}{q_k}$」を $k$ についての帰納法で示す。$k=0,1$ は定義の直後に確かめた。
$k\ge1$ で成り立つとして、$k+1$ の場合を示す。定義の直後の式により
$$ [a_0;a_1,\ldots,a_k,a_{k+1}]=[a_0;a_1,\ldots,a_{k-1},b],\qquad b=a_k+\frac1{a_{k+1}} $$
である。右辺は成分が $k+1$ 個の連分数なので、帰納法の仮定を使える。$p_{k-1},p_{k-2},q_{k-1},q_{k-2}$ は $a_0,\ldots,a_{k-1}$ だけで決まるので、右辺の連分数でも同じ値である。よって
$$ [a_0;\ldots,a_{k-1},b]=\frac{bp_{k-1}+p_{k-2}}{bq_{k-1}+q_{k-2}} $$
である。分子と分母に $a_{k+1}$ を掛けて、$b\,a_{k+1}=a_ka_{k+1}+1$ を使うと
$$ \frac{(a_ka_{k+1}+1)p_{k-1}+a_{k+1}p_{k-2}}{(a_ka_{k+1}+1)q_{k-1}+a_{k+1}q_{k-2}} =\frac{a_{k+1}\overbrace{(a_kp_{k-1}+p_{k-2})}^{=p_k}+p_{k-1}}{a_{k+1}\underbrace{(a_kq_{k-1}+q_{k-2})}_{=q_k}+q_{k-1}} =\frac{p_{k+1}}{q_{k+1}} $$
となる。
$D_k=p_kq_{k-1}-p_{k-1}q_k$ とおく。$D_{-1}=p_{-1}q_{-2}-p_{-2}q_{-1}=1\cdot1-0\cdot0=1=(-1)^{-2}$ である。$k\ge0$ では漸化式を代入して
$$ \begin{aligned} D_k&=(a_kp_{k-1}+p_{k-2})q_{k-1}-p_{k-1}(a_kq_{k-1}+q_{k-2})\\ &=p_{k-2}q_{k-1}-p_{k-1}q_{k-2}=-D_{k-1} \end{aligned} $$
である（$a_kp_{k-1}q_{k-1}$ の項が打ち消し合う）。符号が 1 つずつ入れかわるので $D_k=(-1)^{k-1}$ である。
漸化式は整数の足し算と掛け算だけなので、$p_k,q_k$ は整数である。$d$ が $p_k$ と $q_k$ の正の公約数なら、(2) の左辺を割り切るので $d\mid(-1)^{k-1}$、つまり $d=1$ である。$\square$

近似分数と 1 次不定方程式

ex-cfh-table の $k=3$ の列から $157\cdot13-30\cdot68=2041-2040=1$ である。つまり $157x-68y=1$ の整数解 $x=13$、$y=30$ が、1 つ手前の近似分数 $\dfrac{30}{13}$ から読める。拡張互除法（整数の割り算と互除法の Bézout の等式）を表で行ったのと同じである。
$\sqrt2$ を打ち切った分数 $1,\dfrac32,\dfrac75,\dfrac{17}{12}$ は、成分 $1,2,2,2$ から $p_k=2p_{k-1}+p_{k-2}$ で $1,3,7,17$、$q_k=2q_{k-1}+q_{k-2}$ で $1,2,5,12$ と求まる。thm-cfh-recurrence の (2) の式は $3\cdot1-1\cdot2=1$、$7\cdot2-3\cdot5=-1$、$17\cdot5-7\cdot12=1$ である。

漸化式を行列の積で書く見方を開く

thm-cfh-recurrence の漸化式は、行列で

$$\begin{pmatrix}p_k&p_{k-1}\\q_k&q_{k-1}\end{pmatrix}=\begin{pmatrix}p_{k-1}&p_{k-2}\\q_{k-1}&q_{k-2}\end{pmatrix}\begin{pmatrix}a_k&1\\1&0\end{pmatrix}$$

と書ける。$\begin{pmatrix}p_{-1}&p_{-2}\\q_{-1}&q_{-2}\end{pmatrix}$ は単位行列なので、$\begin{pmatrix}p_k&p_{k-1}\\q_k&q_{k-1}\end{pmatrix}=\begin{pmatrix}a_0&1\\1&0\end{pmatrix}\begin{pmatrix}a_1&1\\1&0\end{pmatrix}\cdots\begin{pmatrix}a_k&1\\1&0\end{pmatrix}$ である。各因子の行列式は $-1$ なので、左辺の行列式 $p_kq_{k-1}-p_{k-1}q_k$ は $(-1)^{k+1}=(-1)^{k-1}$ になる。これが (2) の別証明である。行列と分数の対応は分数型の漸化式と1次分数変換で、行列で漸化式を扱う方法は漸化式の行列表示で扱った。

無理数の連分数

ex-cfh-start-sqrt2 の手順を一般の実数に行う。

連分数展開の手順

実数 $x$ について、$x_0=x$ とし、$k=0,1,2,\ldots$ の順に
$$ a_k=\lfloor x_k\rfloor\quad(x_k\text{ 以下の最大の整数}),\qquad x_{k+1}=\frac1{x_k-a_k}\quad(x_k\ne a_k\text{ のとき}) $$
と定める。$x_k=a_k$ となったら止める。得られた $a_0,a_1,a_2,\ldots$ を $x$ の 連分数展開 といい、止まらないときは $x=[a_0;a_1,a_2,\ldots]$ と書く。$x_{k+1}$ を 完全商 という。

$x_k\ne a_k$ なら $0< x_k-a_k<1$ なので $x_{k+1}>1$ で、$k\ge1$ の成分は $a_k\ge1$ である。定義から $x_k=a_k+\dfrac1{x_{k+1}}$ なので、定義の直後の式を繰り返し使うと
$$ x=[a_0;a_1,\ldots,a_k,x_{k+1}] $$
が成り立つ（最後の成分 $x_{k+1}$ は正の実数）。$x$ が有理数なら、この手順は互除法そのもので、prop-cfh-rational の展開が得られて止まる。$x$ が無理数なら、$x_k$ はすべて無理数で（$x_{k+1}$ が有理数なら $x_k=a_k+\frac1{x_{k+1}}$ も有理数になる）、手順は止まらない。

黄金比の連分数と Fibonacci 数

$\varphi=\dfrac{1+\sqrt5}2=1.618\ldots$ は $\varphi^2=\varphi+1$ を満たす。$a_0=\lfloor\varphi\rfloor=1$ で、$\varphi(\varphi-1)=\varphi^2-\varphi=1$ から
$$ x_1=\frac1{\varphi-1}=\varphi $$
である。以後も同じなので $\varphi=[1;1,1,1,\ldots]$ である。近似分数の漸化式は $p_k=p_{k-1}+p_{k-2}$、$q_k=q_{k-1}+q_{k-2}$ で、$p_{-1}=1$、$p_0=1$、$q_{-1}=0$、$q_0=1$ から
$$ \frac{p_k}{q_k}=\frac11,\ \frac21,\ \frac32,\ \frac53,\ \frac85,\ \frac{13}8,\ \ldots=\frac{F_{k+2}}{F_{k+1}} $$
となる（$F_n$ は Fibonacci 数）。thm-cfh-recurrence の (2) は $F_{k+2}F_k-F_{k+1}^2=(-1)^{k-1}$ で、(3) は隣り合う Fibonacci 数が互いに素であることを言っている（Fibonacci数の整数の性質）。

円周率の連分数

$\pi=3.14159265\ldots$ の小数の値を使って手順を進めると
$$ x_1=\frac1{0.14159265\ldots}=7.0625\ldots,\quad x_2=15.9965\ldots,\quad x_3=1.0034\ldots,\quad x_4=292.63\ldots $$
で、$\pi=[3;7,15,1,292,\ldots]$ である（数値計算）。近似分数は
$$ 3,\qquad \frac{22}7,\qquad \frac{333}{106},\qquad \frac{355}{113},\qquad \frac{103993}{33102},\ \ldots $$
である。たとえば $p_1=7\cdot3+1=22$、$q_1=7$、$p_2=15\cdot22+3=333$、$q_2=15\cdot7+1=106$、$p_3=333+22=355$、$q_3=106+7=113$ である。

主定理 2：近似分数は左右交互に近づく

近似分数の近づき方

無理数 $x$ の連分数展開を $x=[a_0;a_1,a_2,\ldots]$、完全商を $x_{k+1}$、近似分数を $\dfrac{p_k}{q_k}$ とする。$k\ge0$ について次が成り立つ。
(1) $x-\dfrac{p_k}{q_k}=\dfrac{(-1)^k}{q_k\,(x_{k+1}q_k+q_{k-1})}$ である。特に、$k$ が偶数なら $\dfrac{p_k}{q_k}< x$、$k$ が奇数なら $\dfrac{p_k}{q_k}>x$ である。
(2) $\left\lvert x-\dfrac{p_k}{q_k}\right\rvert<\dfrac1{q_kq_{k+1}}\le\dfrac1{q_k^2}$ である。
(3) $k\ge1$ で $q_k\ge k$ であり、$\dfrac{p_k}{q_k}$ は $k\to\infty$ で $x$ に収束する。

$x=[a_0;a_1,\ldots,a_k,x_{k+1}]$ は、成分が $a_0,\ldots,a_k,x_{k+1}$ の連分数である。thm-cfh-recurrence の (1) を、最後の成分を $x_{k+1}$ としてこの連分数に使うと
$$ x=\frac{x_{k+1}p_k+p_{k-1}}{x_{k+1}q_k+q_{k-1}} $$
である（$p_k,q_k$ までは $a_0,\ldots,a_k$ で決まるので、もとの近似分数と同じである）。通分して thm-cfh-recurrence の (2) を使うと
$$ x-\frac{p_k}{q_k}=\frac{q_k(x_{k+1}p_k+p_{k-1})-p_k(x_{k+1}q_k+q_{k-1})}{q_k(x_{k+1}q_k+q_{k-1})}=\frac{p_{k-1}q_k-p_kq_{k-1}}{q_k(x_{k+1}q_k+q_{k-1})}=\frac{-(-1)^{k-1}}{q_k(x_{k+1}q_k+q_{k-1})} $$
で、分子は $(-1)^k$ である。分母は正なので、符号は $(-1)^k$ で決まる。
$x_{k+1}$ は無理数で $a_{k+1}=\lfloor x_{k+1}\rfloor$ なので、$x_{k+1}>a_{k+1}$ である。よって
$$ x_{k+1}q_k+q_{k-1}>a_{k+1}q_k+q_{k-1}=q_{k+1} $$
で、(1) から $\left\lvert x-\dfrac{p_k}{q_k}\right\rvert<\dfrac1{q_kq_{k+1}}$ である。さらに $q_{k+1}=a_{k+1}q_k+q_{k-1}\ge q_k$（$a_{k+1}\ge1$、$q_{k-1}\ge0$）なので $\dfrac1{q_kq_{k+1}}\le\dfrac1{q_k^2}$ である。
$q_1=a_1\ge1$ である。$k\ge1$ では $q_{k-1}\ge1$ なので $q_{k+1}=a_{k+1}q_k+q_{k-1}\ge q_k+1$ である。よって $q_k\ge k$ で、(2) から $\left\lvert x-\dfrac{p_k}{q_k}\right\rvert<\dfrac1{q_k^2}\le\dfrac1{k^2}$ となり、$k\to\infty$ で $0$ に近づく。$\square$

$\sqrt2$ と $\pi$ で確かめる

$\sqrt2=1.41421356\ldots$ の近似分数と誤差は次のとおりである（数値計算）。

$k$	$\dfrac{p_k}{q_k}$	値	$\sqrt2-\dfrac{p_k}{q_k}$	$\dfrac1{q_kq_{k+1}}$
$0$	$\dfrac11$	$1$	$0.4142$	$0.5$
$1$	$\dfrac32$	$1.5$	$-0.0858$	$0.1$
$2$	$\dfrac75$	$1.4$	$0.01421$	$0.01667$
$3$	$\dfrac{17}{12}$	$1.41667$	$-0.002453$	$0.002874$
$4$	$\dfrac{41}{29}$	$1.41379$	$0.0004205$	$0.0004926$
$5$	$\dfrac{99}{70}$	$1.414286$	$-0.00007215$	$0.00008453$

誤差の符号は $+,-,+,-,\ldots$ と交互で、大きさは上界 $\dfrac1{q_kq_{k+1}}$ より小さい。図 2 は、近似分数から $\sqrt2$ を引いた値 $\dfrac{p_k}{q_k}-\sqrt2$（表の列と符号が逆）を並べ、近似分数が $\sqrt2$ の下と上に交互に来るようすを示したものである。

$\pi$ では、$\dfrac{22}7-\pi=0.00126\ldots<\dfrac1{7\cdot106}=0.00135\ldots$、$\dfrac{355}{113}-\pi=2.6676\ldots\times10^{-7}<\dfrac1{113\cdot33102}=2.6734\ldots\times10^{-7}$ である。$\dfrac{355}{113}$ は、上界 $\dfrac1{q_3q_4}$ の $q_4=33102$ が大きいので、分母 $113$ のわりにとても近い。これは次の成分 $a_4=292$ が大きいことから来ている（図 3）。

√2 の近似分数から √2 を引いた値。縦軸は対数の目盛りで、符号は正と負が交互に並び、大きさは急速に小さくなる
π の近似分数の誤差（青）と上界 1/(q_k q_(k+1))（灰色の破線）を対数の目盛りで並べた図。k=3 の 355/113 の後で誤差が大きく下がる
(2) の $\dfrac1{q_k^2}$ の評価から、分母の 2 乗の逆数より近い分数がいくらでもあることが分かる。

分母の 2 乗より近い分数

無理数 $x$ に対し、$\left\lvert x-\dfrac pq\right\rvert<\dfrac1{q^2}$ を満たす既約分数 $\dfrac pq$（$q\ge1$）は無限に多くある。

thm-cfh-approx の (2) により、どの近似分数 $\dfrac{p_k}{q_k}$ も不等式を満たし、thm-cfh-recurrence の (3) により既約である。(3) の証明から $k\ge1$ で $q_1< q_2< q_3<\cdots$ なので、近似分数 $\dfrac{p_1}{q_1},\dfrac{p_2}{q_2},\ldots$ は分母の異なる既約分数で、互いに異なる。よって無限に多い。$\square$

実数とは何か：無理数の証明では、この事実を「証明しない」として紹介した。連分数を使うと、ここまでの計算だけで示せる。

例と反例

外す条件	反例	成り立たなくなること
最後の成分を $2$ 以上にする約束	$[2;3,4,5]=[2;3,4,4,1]$	表し方がただ 1 通り
成分 $a_1,a_2,\ldots$ が正	$[1;1,-1]$	連分数の値が定まる
近似分数を使う	小数の打ち切り $3.14=\dfrac{157}{50}$	分母の小さな分数でよく近似する

反例：最後の成分を $1$ にすると 2 通りに書ける

$[2;3,4,4,1]$ を内側から計算すると、$4+\dfrac11=5$ なので $[2;3,4,5]=\dfrac{157}{68}$ と同じ値になる。互除法の最後の段 $5=5\cdot1$ を $5=4\cdot1+1$、$1=1\cdot1$ と割り直したのと同じである。rem-cfh-unique の約束はこれを除くためのものである。

反例：負の成分を許すと 0 で割る

$[1;1,-1]=1+\cfrac1{1+\cfrac1{-1}}=1+\dfrac1{0}$ となり、値が定まらない。近似分数の漸化式でも $q_2=a_2q_1+q_0=(-1)\cdot1+1=0$ で、分母が $0$ になる。def-cfh-cf で $a_1,a_2,\ldots$ を正にしたのは、分母が $0$ にならないようにするためである。

反例：小数の打ち切りはよい近似とは限らない

$\pi$ を小数第 2 位で打ち切ると $3.14=\dfrac{157}{50}$ で、誤差は $\pi-3.14=0.00159\ldots$ である。近似分数 $\dfrac{22}7$ の誤差は $\dfrac{22}7-\pi=0.00126\ldots$ で、分母は $7$ と小さいのに誤差も小さい。小数第 4 位までの $3.1416=\dfrac{3927}{1250}$ の誤差 $7.3\ldots\times10^{-6}$ も、分母 $113$ の $\dfrac{355}{113}$ の誤差 $2.7\ldots\times10^{-7}$ より大きい。分母が $50$ 以下の分数の中で $\pi$ に最も近いのは $\dfrac{22}7$、分母が $113$ 以下の中で最も近いのは $\dfrac{355}{113}$ である（分母ごとに最も近い分子を探す数値計算で確かめた）。

演習

有理数の近似分数

$\dfrac{43}{30}$ の連分数展開と、すべての近似分数を求めよ。さらに、近似分数を使って $43x-30y=1$ の整数解を 1 つ求めよ。

解答を開く

ex-cfh-rational の (1) より $\dfrac{43}{30}=[1;2,3,4]$ である。漸化式で $p_k=1,3,10,43$、$q_k=1,2,7,30$ となり、近似分数は $1,\dfrac32,\dfrac{10}7,\dfrac{43}{30}$ である。thm-cfh-recurrence の (2) で $k=3$ とすると $43\cdot7-10\cdot30=(-1)^2=1$ なので、$x=7$、$y=10$ が解である。

$\sqrt3$ の連分数

$\sqrt3$ の連分数展開が $[1;1,2,1,2,1,2,\ldots]$ となることを示し、近似分数を $6$ 個求めよ。そのうち $p^2-3q^2=1$ を満たすものを挙げよ。

解答を開く

$x_0=\sqrt3$、$a_0=1$、$x_1=\dfrac1{\sqrt3-1}=\dfrac{\sqrt3+1}2=1.366\ldots$、$a_1=1$、$x_2=\dfrac1{\frac{\sqrt3+1}2-1}=\dfrac2{\sqrt3-1}=\sqrt3+1=2.732\ldots$、$a_2=2$、$x_3=\dfrac1{\sqrt3+1-2}=\dfrac1{\sqrt3-1}=x_1$ である。$x_3=x_1$ なので以後は $1,2$ を繰り返す。近似分数は $1,2,\dfrac53,\dfrac74,\dfrac{19}{11},\dfrac{26}{15}$ で、$2^2-3\cdot1^2=1$、$7^2-3\cdot4^2=1$、$26^2-3\cdot15^2=676-675=1$ を満たす。

大学数学で見る：循環する連分数

$\sqrt2=[1;2,2,\ldots]$、$\varphi=[1;1,1,\ldots]$、$\sqrt3=[1;1,2,1,2,\ldots]$ は、ある所から先で成分が周期的にくり返す。これらはどれも整数係数の 2 次方程式の解（2 次の無理数）である。一般に、無限の単純連分数がある所から先で周期的になるのは、その値が 2 次の無理数であるとき、かつそのときに限る（Lagrange の定理。Ste17 Theorem 5.5.5。この記事では証明しない）。$\sqrt2$ の近似分数 $\dfrac32$、$\dfrac{17}{12}$、$\dfrac{99}{70}$ が $p^2-2q^2=1$ を満たし、演習の $\sqrt3$ でも同じことが起こるのは偶然ではない。この方程式が次の記事 Pell方程式（高校数学）の主題である。

最良近似と $e$ の連分数を開く

近似分数は、分母がそれ以下の分数の中で最もよい近似になっていることが知られている（Ste17 の §5.2 の記述。この記事では証明しない）。ex-cfh-cx-decimal の数値計算はその例である。

$e=2.71828\ldots$ の連分数は $[2;1,2,1,1,4,1,1,6,\ldots]$ と、$1,1$ をはさんで $2,4,6,\ldots$ が現れる規則的な形になる（Ste17 §5.4 に証明がある）。一方 $\pi$ の成分 $3,7,15,1,292,\ldots$ については、Ste17 の §5.3 が、$e$ と違って目に見える規則がないと述べている。

さらに先へ

近似分数の漸化式 $\dfrac{p_k}{q_k}=\dfrac{a_kp_{k-1}+p_{k-2}}{a_kq_{k-1}+q_{k-2}}$ は、分子どうし・分母どうしを足して中間の分数を作る操作（等式の証明と比例式）を $\dfrac{p_{k-2}}{q_{k-2}}$ に $\dfrac{p_{k-1}}{q_{k-1}}$ を $a_k$ 回くり返し足したものと見られる。
$x\mapsto a+\dfrac1x$ の形の 1 次分数変換をくり返す見方は分数型の漸化式と1次分数変換、黄金比の連分数と正五角形の関係は正五角形と黄金比、$\dfrac{22}7$ と $\pi$ の差を積分で表す方法は積分で円周率を評価するにある。
近似分数の漸化式・既約性・左右交互に近づくこと・誤差の評価は Ste17 の §5.2〜§5.3（Proposition 5.2.5、5.2.7、Corollary 5.2.10、Proposition 5.2.13、5.2.14、Theorem 5.3.10、Corollary 5.3.11）にある。大学向けの記事は連分数である。