連分数 | 初等整数論

1 有限連分数と互除法

定義 1.1. 整数 $a_0$ と正整数 $a_1,\ldots,a_k$ から作る

[a_0;a_1,\ldots,a_k] =a_0+\cfrac1{a_1+\cfrac1{\cdots+\cfrac1{a_k}}}

を有限単純連分数 (finite simple continued fraction) という。 $k=0$ のときは $[a_0]=a_0$ とする。

命題 1.2. すべての有理数は、 $a_0$ を整数、 $a_1,\ldots,a_k$ を正整数とする有限単純連分数で表される。 $k\ge1$ のときに末項を $a_k\ge2$ とする条件のもとで、この表示はただ一つである。整数は一項の $[a_0]$ で表され、 $a_0$ に $2$ 以上という条件は課さない。逆に、すべての有限単純連分数の値は有理数である。

証明. 有理数を $p/q$ と書く。ただし $p\in\Z$ 、 $q\in\NN$ とする。除法の原理により $p=a_0q+r$ 、 $0\le r<q$ と書く。 $r=0$ なら $p/q=[a_0]$ である。 $r>0$ なら

\frac pq=a_0+\frac1{q/r}

として $q/r$ に同じ操作を行う。この操作で現れる分母は余りの列であり、正整数のまま狭義に減少するので、有限回で停止する。二番目以降に整数部分を取り出す数は $1$ より大きいから、商は正整数である。最後に余りが $0$ になる数も $1$ より大きいので、整数である末項は $2$ 以上となる。

末項が $2$ 以上の表示では、後ろから順に計算すると、各 $[a_j;\ldots,a_k]$ （ $1\le j\le k$ ）は $1$ より大きい。したがって、 $k\ge1$ なら $a_0<[a_0;a_1,\ldots,a_k]<a_0+1$ であり、 $a_0$ はもとの数以下の最大の整数に等しい。整数部分を引いて逆数を取ると次の末尾の式が定まり、同じ議論で各項が順に定まる。整数に達した時点では、複数項の表示は上の狭義不等式に反するから、一項で停止する。よって、項と表示の長さは一意である。

有限単純連分数は、正の末尾から有限回の有理数の四則計算で求められるので、その値は有理数である。▨

例 1.3. $43/30$ の整数部分を取り出して逆数を取ると、

\frac{43}{30}=1+\frac{13}{30}=1+\frac1{30/13},\qquad \frac{30}{13}=2+\frac4{13}=2+\frac1{13/4},\qquad \frac{13}{4}=3+\frac14

となる。したがって $43/30=[1;2,3,4]$ である。この計算に現れる項は、ユークリッドの互除法

43=1\cdot30+13,\qquad 30=2\cdot13+4,\qquad 13=3\cdot4+1,\qquad 4=4\cdot1

の商の列である。

例 1.4. 末項の条件を外すと

\frac{43}{30}=[1;2,3,4]=[1;2,3,3,1]

となる。一般に、 $k\ge1$ 、 $a_k\ge2$ のとき、 $a_k=(a_k-1)+1/1$ から

[a_0;a_1,\ldots,a_k]=[a_0;a_1,\ldots,a_k-1,1]

が成り立つ。負の数では、 $-7/3=-3+2/3$ から $-7/3=[-3;1,2]$ となる。整数の表示は、たとえば $0=[0]$ 、 $-2=[-2]$ である。

2 無理数の展開

定義 2.1. 無理数 $\alpha$ に対し、 $\alpha_0=\alpha$ とおき、各 $j\in\N$ について $a_j$ を $\alpha_j$ 以下の最大の整数とし、

\alpha_{j+1}=\frac1{\alpha_j-a_j}

と定める。各 $\alpha_j$ を完全商 (complete quotient) といい、項の列を $\alpha=[a_0;a_1,a_2,\ldots]$ と書く。

$\alpha_j$ が無理数なら、 $\alpha_j-a_j$ は $0$ と $1$ の間の無理数です。その逆数 $\alpha_{j+1}$ も無理数であり、 $1$ より大きいため、操作は途中で止まりません。 $j\ge1$ では $a_j\ge1$ となります。

例 2.2. $\sqrt2$ では

\sqrt2=1+\frac1{\sqrt2+1},\qquad \sqrt2+1=2+\frac1{\sqrt2+1}

となるので、 $\sqrt2=[1;2,2,2,\ldots]$ である。黄金比 $x=(1+\sqrt5)/2$ は $1<x<2$ と $x=1+1/x$ を満たすので、 $x=[1;1,1,1,\ldots]$ である。

注意 2.3. 無理数の単純連分数が最終的に周期的になることと、その無理数が実二次無理数であることは同値である。実二次無理数とは、有理数係数の二次方程式の無理な実数解、すなわち $\Q$ 上の次数が $2$ の実数をいう。単なる $\sqrt D$ に限らず、有理数 $r,s$ と平方数でない正整数 $D$ を用いた $r+s\sqrt D$ （ $s\ne0$ ）も含む。ここでは周期性の一般定理は証明しない。

注意 2.4. 無限連分数の値を近似分数の列の極限として扱うには、その列の収束を示す必要がある。数列の極限と収束の理論は §D1 ε-論法と基礎解析で扱う。以下の誤差の等式は、与えられた無理数に対する有限回の代入から導く。

3 近似分数の計算と誤差

定義 3.1. $a_0$ を整数とし、 $a_1,a_2,\ldots$ を正整数とする。単純連分数を第 $k$ 項で打ち切った有限連分数 $[a_0;a_1,\ldots,a_k]$ を、第 $k$ 近似分数 (convergent) という。収束分数ともいう。近似分数では、打ち切った位置を保つため、末項が $1$ の表示もそのまま用いる。

命題 3.2. $a_0\in\Z$ 、 $a_j\in\NN$ （ $j\ge1$ ）とする。整数列 $p_k,q_k$ を

p_{-2}=0,\quad p_{-1}=1,\quad q_{-2}=1,\quad q_{-1}=0,

p_k=a_kp_{k-1}+p_{k-2},\qquad q_k=a_kq_{k-1}+q_{k-2}\qquad(k\ge0)

によって定める。すべての $k\ge0$ について $q_k>0$ であり、

[a_0;a_1,\ldots,a_k]=\frac{p_k}{q_k},\qquad p_kq_{k-1}-p_{k-1}q_k=(-1)^{k+1}

が成り立つ。 $p_k/q_k$ は既約分数である。任意の実数 $t>0$ に対し、末尾を $a_k+1/t$ とした式 $F_k(t)$ は

F_k(t)=[a_0;a_1,\ldots,a_k+1/t] =\frac{p_kt+p_{k-1}}{q_kt+q_{k-1}}

を満たす。 $k=0$ のとき、左辺は $a_0+1/t$ を表す。

さらに、無理数 $\alpha$ の完全商 $\alpha_j$ と項 $a_j$ から同じ漸化式で $p_k,q_k$ を定めると、すべての $k\ge0$ について

\alpha=\frac{p_k\alpha_{k+1}+p_{k-1}}{q_k\alpha_{k+1}+q_{k-1}},\qquad \alpha-\frac{p_k}{q_k} =\frac{(-1)^k}{q_k(q_k\alpha_{k+1}+q_{k-1})},

\left|\alpha-\frac{p_k}{q_k}\right| =\frac1{q_k(q_k\alpha_{k+1}+q_{k-1})} <\frac1{q_kq_{k+1}}

が成り立つ。

証明. $q_0=1$ 、 $q_1=a_1\ge1$ と漸化式から、すべての $k\ge0$ について $q_k>0$ である。 $F_0(t)=a_0+1/t=(p_0t+p_{-1})/(q_0t+q_{-1})$ である。 $k\ge1$ では、帰納法の仮定と漸化式から

F_k(t)=F_{k-1}(a_k+1/t) =\frac{(a_kp_{k-1}+p_{k-2})t+p_{k-1}} {(a_kq_{k-1}+q_{k-2})t+q_{k-1}} =\frac{p_kt+p_{k-1}}{q_kt+q_{k-1}}

を得る。 $k\ge1$ の近似分数は $F_{k-1}(a_k)=p_k/q_k$ であり、 $k=0$ では $[a_0]=p_0/q_0$ である。

$p_0q_{-1}-p_{-1}q_0=-1$ であり、 $k\ge1$ では

p_kq_{k-1}-p_{k-1}q_k =-(p_{k-1}q_{k-2}-p_{k-2}q_{k-1})

なので、行列式の等式が帰納的に従う。 $p_k,q_k$ の共通の正の約数はこの差も割るので、 $p_k,q_k$ は互いに素である。

$\alpha_j=a_j+1/\alpha_{j+1}$ を有限回代入すると、 $\alpha=F_k(\alpha_{k+1})$ である。この表示と行列式の等式から

\alpha-\frac{p_k}{q_k} =\frac{p_{k-1}q_k-p_kq_{k-1}}{q_k(q_k\alpha_{k+1}+q_{k-1})} =\frac{(-1)^k}{q_k(q_k\alpha_{k+1}+q_{k-1})}

を得る。 $\alpha_{k+1}>a_{k+1}$ なので、

q_k\alpha_{k+1}+q_{k-1}>a_{k+1}q_k+q_{k-1}=q_{k+1}.

両辺が正であることから、誤差の不等式が従う。▨

例 3.3. $43/30=[1;2,3,4]$ の近似分数は、漸化式から

\frac11,\qquad\frac32,\qquad\frac{10}{7},\qquad\frac{43}{30}

となる。最後の近似分数は元の有理数と一致する。

例 3.4. $\sqrt2=[1;2,2,\ldots]$ の近似分数は、漸化式から

1,\quad\frac32,\quad\frac75,\quad\frac{17}{12},\quad \frac{41}{29},\quad\frac{99}{70},\quad\frac{239}{169}

となる。命題 3.2の誤差評価により

\left|\sqrt2-\frac{99}{70}\right| <\frac1{70\cdot169}=\frac1{11830}<\frac1{10000}

である。

問題 3.5. 整数 $p$ と正整数 $q$ が $1<p/q<2$ を満たすとする。

\left|\sqrt2-\frac pq\right|>\frac1{4q^2}

を示せ。さらに、 $q\ge4$ である同じ範囲の分数について、 $|\sqrt2-p/q|\le1/q^3$ は成り立たないことを示せ。

解答.

$\sqrt2$ は無理数なので、整数 $p^2-2q^2$ は $0$ ではなく、 $|p^2-2q^2|\ge1$ である。 $1<p/q<2$ と $1<\sqrt2<2$ から

\left|\sqrt2-\frac pq\right| =\frac{|p^2-2q^2|}{q^2(p/q+\sqrt2)} \ge\frac1{q^2(p/q+\sqrt2)}>\frac1{4q^2}

となる。 $q\ge4$ なら $1/q^3\le1/(4q^2)$ なので、 $|\sqrt2-p/q|\le1/q^3$ は成り立たない。▨

例 3.6. 円周率の展開は $\pi=[3;7,15,1,292,\ldots]$ であり、

[3;7]=\frac{22}{7}=3.1428\ldots,\qquad [3;7,15,1]=\frac{355}{113}=3.1415929\ldots

となる。 $355/113$ の表示は末項が $1$ であるが、第 $3$ 近似分数として打切り位置を保っている。 $22/7$ はアルキメデスの円周率の評価に現れ、 $355/113$ は五世紀の中国の数学者祖沖之による近似として知られる。 $355/113$ は三桁の分母で円周率と小数第六位まで一致する。

注意 3.7. 無理数 $\alpha$ の第 $k$ 近似分数を $p_k/q_k$ とする。近似分数には第二種の最良近似性がある。 $0<q<q_{k+1}$ を満たす整数 $p,q$ について、 $p/q\ne p_k/q_k$ なら

|q_k\alpha-p_k|\le|q\alpha-p|

が成り立つ。ここでは、この定理を証明しない。

閑話休題：連分数と暦 季節の周期である回帰年は約 $365.2422$ 日である。米国海軍天文台の解説では、グレゴリオ暦の平均年を $365.2425$ 日としている。 $365$ 日の暦と回帰年との一年あたりのずれ $0.2422$ 日を閏日で補うには、閏日を置く回数と年数との比を $0.2422$ に近づければよい。 $0.2422=[0;4,7,1,3,\ldots]$ の近似分数は

\frac14,\qquad\frac7{29},\qquad\frac8{33},\qquad\frac{31}{128},\qquad\ldots

となる。 $1/4$ は四年に一回、 $8/33$ は三十三年に八回の閏日を置く割合である。グレゴリオ暦では四百年に九十七回の閏日を置き、その割合は $97/400$ である。 $97/400$ は上の連分数の近似分数ではない。数値 $0.2422$ に対する誤差を比較すると、

\left|\frac8{33}-0.2422\right|=\frac{37}{165000} <\frac3{10000}=\left|\frac{97}{400}-0.2422\right|

となる。

歴史上、四年に一回の閏日を置く方式はユリウス暦に採用された。十一世紀のペルシャの数学者・詩人ウマル・ハイヤームが関わった暦には、三十三年に八回の閏日を置く方式が帰属されている。また、十七世紀のホイヘンスは、太陽系の模型を歯車で作る際に、惑星の公転周期の比を歯数の比で近似するために連分数を用いたとされる。歯数を整数で選ぶ問題でも、分母を抑えた有理数近似が必要になる。

§A4.11連分数

1 有限連分数と互除法

2 無理数の展開

3 近似分数の計算と誤差

例題

演習

前提記事